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

Question

如果我有一个未排序的大型整数集合（假设有2 ^ 20个），并且想要生成每个k个元素（其中k很小，例如5）的子集，并按它们的总和递增排序，则最有效的方法是什么？

我需要以这种方式生成这些子集的原因是，我想找到满足某个条件的最小总和k元素子集，并因此在生成的每个k元素子集上应用该条件。

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

这里有一个类似的问题： 算法以它们的乘积顺序获取列表的每个可能子集，而无需构建和排序整个列表（即Generators），但由于集合n非常大，所以不适用于我的需求。

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

- Vincent Tjeng

---

你想生成所有k阶子集吗？这可能会掩盖排序的效果，因为对于k >= 2，O(n * log n) < O(all subsets)。 - user1952500

什么是条件？你应该在生成候选项时应用它-否则对于无限制k的一般情况，这个问题听起来像背包问题-至少对我来说是这样。 - 500 - Internal Server Error

@user1952500 我不想生成所有子集 - 我希望在进行测试时逐个测试它们。 - Vincent Tjeng

@500-服务器内部错误，条件有点长，我无法在这里贴出来，但是我将能够在生成候选项时应用它。这正是为什么我想按照它们的总和递增地生成候选项的原因，这样我就不必检查更多的候选项。 - Vincent Tjeng

你需要满足条件的所有元组吗？你能预先估计这些元组的概率吗？ - user1952500

Answer 1

即使只有千分之一的k大小的集合符合您的条件，要测试的组合数量仍然太多了。我相信运行时间与nCk（n选择k）成比例，其中n是您的未排序列表的大小。Andrew Mao的答案中有一个指向此值的链接。10 ^ 28/1000仍然是10 ^ 25。即使每秒进行1000次测试，这仍然需要10 ^ 22秒。= 10 ^ 14年。

如果允许的话，我认为您需要从大型集合中消除重复数字。每个删除的重复项都会大大减少您需要执行的评估次数。对列表进行排序，然后杀死重复项。

此外，您是否在寻找最佳答案？谁将验证答案，需要多长时间？我建议实施遗传算法并在一夜之间运行多个实例（尽可能长的时间）。这将在比宇宙持续时间短得多的时间内产生非常好的答案。

- mfa

---

你的逻辑有错误。你的数学计算表明，10^25个集合中只有1个符合条件。 - Andrew Mao

10^28 / 10^3 = 10^25个满足条件的集合。其中10^3来自提问者对你的回答的评论。 - mfa

如果每10^3个集合中有1个符合条件，那么你只需要测试小于10^3的几个集合就能找到满足条件的例子，而不是10^25个。这就是你逻辑上的错误，因此也不需要10^14年才能找到一个例子。 - Andrew Mao

Answer 2

如果您想要对小子集（称为P）进行的属性相当普遍，则概率方法可能很有效：

1. 对n个整数进行排序（对于数百万个整数，即10到100 MB的RAM，这不应该是问题），并求出k-1个最小数的总和。将其称为offset。
2. 生成一个随机的k子集（例如，通过取模n来抽样k个随机数），并检查它是否具有P属性。
3. 在匹配时，记录子集的总和。从中减去offset以找到等效总和的任何k子集中最大元素的上限。
4. 将您的n个整数集限制为小于或等于此界限。
5. 重复（转到2）直到在固定迭代次数内未发现匹配项。

请注意，初始排序时间复杂度为O(n log n)。步骤4中的二分查找时间复杂度为O(log n)。

显然，如果P很罕见，随机尝试可能不会匹配，那么这对你没有好处。

- phs

Answer 3

您是指20个整数，还是2^20个整数？如果是真的有2^20个整数，那么在找到满足条件的子集之前，您可能需要经过大量的(2^20 choose 5)个子集。在现代100k MIPS CPU上，假设只需一个指令即可计算一个集合并评估该条件，即使只需遍历该整个集合，也需要3千亿年。因此，如果您甚至需要遍历其中的一小部分，它也不会在您的有生之年内完成。

即使整数的数量较小，这似乎是一种相当暴力的解决问题的方式。我猜想你可以将条件表达为混合整数规划中的约束条件，在这种情况下，解决以下问题可能比暴力枚举更快地获得解决方案。假设您的整数为w_i，i从1到N：

min sum(i) w_i*x_i
    x_i binary
    sum over x_i = k
subject to (some constraints on w_i*x_i)

如果你的MIP的线性规划松弛是紧密的，那么你将会很幸运地拥有一种非常有效的解决问题的方法，即便对于2^20个整数也是如此（例如：最大流/最小割问题）。此外，你可以使用列生成的方法来找到解决方案，因为你可能有很多值无法同时解决。

如果你发布更多关于你感兴趣的约束条件的信息，我或其他人可能会为你提出更具体的解决方案，而不涉及暴力枚举。

- Andrew Mao

---

谢谢你的回答！我真的是指大量的整数，数量级达到百万级别。然而，在n的k-子集中，有相当一部分满足我的约束条件（比如每1000个中有1个），所以我可以期望通过枚举最小的5000个子集来找到一个最小解。我会尽快发布具体的问题。 - Vincent Tjeng

我认为编写一个程序，能够按递增顺序生成子集列表而无需先生成完整的子集列表，这仍然是很有趣的，@Andrew。 - Vincent Tjeng

Answer 4

这似乎是MapReduce（http://en.wikipedia.org/wiki/MapReduce）的完美候选者。如果您知道如何智能地将它们分区，以便通过的候选者在每个节点中都平均存在，那么您可能可以获得很高的吞吐量。

完全排序可能并不是真正需要的，因为映射阶段可以处理它。然后，每个节点可以针对k元组验证条件，并将结果输出到一个文件中，稍后可以进行聚合/减少。

如果您知道发生的概率并且不需要所有结果，请尝试查看概率算法以收敛到答案。

- user1952500

---

即使是MapReduce也无法处理10^28个k元组。 - Andrew Mao

是的，但你可能会更快地开始得到结果。我怀疑并不需要所有元组，但在我了解目标和条件之前，我不能确定。 - user1952500

Answer 5

这里有一个大致的方法来实现你所说的。

首先，对列表进行排序。然后，考虑一些长度为5的索引向量v，对应于排序后列表中的位置，其中最大索引是某个数字m，以及另一个索引向量v'，其最大索引为m'>m。所有这样的向量v'的最小和总是大于所有向量v的最小和。

因此，以下是如何循环遍历元素的近似递增和：

sort arr

for i = 1 to N
   for v = 5-element subsets of (1, ..., i)
     set = arr{v}
     if condition(set) is satisfied
       break_loop = true
       compute sum(set), keep set if it is the best so far
   break if break_loop

基本上，这意味着如果您在 (1, ..., n) 中找到一个满足的分配，那么您就不再需要检查 (1, ..., n+1) 的 5 元素组合了，因为任何最大索引为 n+1 的满足分配都将具有更大的总和，您可以在那个集合后停止。然而，没有简单的方法可以循环遍历 (1, ..., n) 的 5 组合，并保证总和始终增加，但至少您可以在某个 n 找到满足的集合后停止检查。

- Andrew Mao

---

说唯一有效的 (1, ...,n) 的 5 元素组合是 (n-4, n-3, n-2, n-1, n)，但实际上 (1, 2, 3, 4, n+1) 也是有效的，当前程序会错过这个更小和的子集吗？ - Vincent Tjeng