algorithm - 如何通过总和枚举一个集合的所有k-组合？

Question

假设我有一组大小为 n 的有限数值。

问题:是否有一种有效的算法来枚举该集合的 k 个组合，以便组合 I 先于组合 J，当且仅当 I 中元素的总和小于或等于J中的元素？

---

显然，可以简单地枚举组合并根据它们的总和对它们进行排序。但是，如果集合很大，则无法对所有组合进行粗略枚举，更不用说排序了。如果我只想获得按总和排序的前 m << choose(n,k) 组合，是否有可能在宇宙热寂之前获得它们？

Answer 1

没有以这种方式枚举集合的多项式算法(除非 P=NP )。

如果有这样的算法(假设是A)，那么我们就可以解决subset sum problem多项式:

1. 运行A
2. 进行二分搜索以找到总和最接近所需数字的子集。

请注意，第 1 步按多项式(假设)运行，第 2 步在 O(log(2^n)) = O(n) 中运行。

结论:由于子集和问题是NP-Complete ，有效地解决这个问题将证明 P=NP - 因此这个问题没有已知的多项式解。

---

编辑:即使问题是 NP-Hard，获取“最小”m 子集也可以在 O(n+2^m) 上完成 通过选择最小的 m 元素，从这些 m 元素生成所有子集 - 并选择其中的最小 m。因此对于相当小的 m 值 - 计算它可能是可行的。