1

我将从我编造的心理练习开始，以使我正在尝试做的事情更容易解释和不那么晦涩难懂。

假设我知道一家名为FRUITS的商店，它拥有无限数量的目前已知的每种水果1。

假设我有一台机器，它使用复杂的组合逻辑将任何一组 M=4 项目从FRUITS转换为不在我给2的 4 中的对象。我可以通过给它 4 个名称来测试我会得到的输出类型，而不会用完水果。

我请一个朋友进入FRUITS，选择总数 >= M的水果（至少有 2 种），他们会给我他们选择的每种水果的名称和数量（例如{Apple: 1, Banana: 3, ... }or[Apple,Banana,...]和[1,3,...]）。

我想创建一个有效的算法（可以使用任何语言来说明）来查找我可以给我的机器的所有唯一输入，而无需检查所有M组合或列出每个水果（即按字典顺序）使用一对列表3 . 我想在没有递归的情况下执行此操作，因为列表可能相当大4。

我目前拥有的函数names作为一个列表，counts作为另一个相同长度的列表（比如说N）5。我希望最终版本输出一个列表m列表，其长度等于唯一组合的数量（m在我之前的类比中为 =4）；这些列表将保存names/counts列表的索引（用于说明的伪代码 - 请注意以下返回值 1-indexed）：

function (names: [A,B,C], counts: [2,2,1], m = 4) {
   // ...
   return [
      [1,1,1],[1,2,1],[2,2,2],[2,3,3]
   ]
   // Transposed matrix form to clearly show the 3 combinations (substituted names for indices)
   //
   //   A A B B
   //   A B B C
   //   A A B C
}

（我选择返回m列表的原因是因为m以后很有可能成为常数）

这实际上是我想做的一个涉及组合优化的更大项目的一部分——即真正的目标是找到最大化/最小化列表中项目共享的定量属性之和所需的组合（例如最大化维生素 C ）。但我觉得这个问题本身就太宽泛或太难了，所以我从我认为的第一步开始。

1在这个世界上，所有同名的水果都完全相同（例如，任何一个苹果都等同于另一个苹果）。
2为简单起见，您可以假设输出不在 FRUITS 中。
3如果回调或代码块可以在找到组合时有效集成（例如，使用我的水果转换器进行测试并创建地图），则可以加分。
4我实际上有一个递归版本可以工作，但我希望有一个更有效的算法，因为看起来我将在 Lua 中工作
5完整性检查在这里并不重要，因为输入将被预先检查

4

0 回答 0