按总和顺序生成 k 个元素子集的算法

Question

如果我有一组未排序的大型 n 整数(比如 2^20)并且想生成 k 的子集每个元素(其中 k 很小，例如 5)按总和的递增顺序排列，最有效的方法是什么？

为什么我需要以这种方式生成这些子集是因为我想找到具有满足特定条件的最小总和的 k 元素子集，因此我会将条件应用于每个 k-生成的元素子集。

另外，算法的复杂度是多少？

这里有一个类似的问题:Algorithm to get every possible subset of a list, in order of their product, without building and sorting the entire list (i.e Generators)关于按产品顺序生成子集，但由于集合 n

的大小非常大，它不符合我的需求

我打算在 Mathematica 中实现该算法，但也可以在 C++ 或 Python 中实现。

Answer 1

如果您想要的小子集属性(称之为 P)相当普遍，那么概率方法可能会很有效:

1. 对 n 个整数进行排序(对于数百万个整数，即 10s 到 100s MB 的 ram，这应该不是问题)，并对 k-1 最小的值求和.将此称为总的偏移量。
2. 生成一个随机的 k 子集(例如，通过采样 k 随机数，mod n)并检查它的 P -ness.
3. 在一场比赛中，记下子集的总和。从中减去 offset 以找到任何 k 的最大元素的上限 - 等效总和的子集。
4. 将您的 n 整数集限制为小于或等于此界限的整数。
5. 重复(转到 2)直到在固定的迭代次数内找不到匹配项。

注意初始排序是 O(n log n)。第 4 步中隐含的二分搜索是 O(log n)。

显然，如果 P 非常罕见，以至于随机 pot-shot 不太可能匹配，这对你没有好处。