3

如果我有一组未排序的大n整数（比如2^20它们），并且想生成k每个元素的子集（k比如小5），它们的总和顺序是递增的，那么最有效的方法是什么？

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

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

这里有一个类似的问题：Algorithm to get every possible subset of a list, in order to their product, without building and sort the entire list (ie Generators) about generate subsets of their product,但它不适合我由于集合的尺寸非常大，因此需要n

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

4

5 回答 5

1

你的意思是 20 个整数，还是 2^20？如果它真的是 2^20，那么您可能需要经过大量（2^20 选择 5）个子集才能找到满足您条件的子集。在现代 100k MIPS CPU 上，假设只有 1 条指令可以计算一个集合并评估该条件，那么通过整个集合仍然需要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 整数（例如：max-flow/min-cut 问题。 ) 此外，您可以使用列生成的方法来找到解决方案，因为您可能有大量无法同时解决的值。

如果您发布更多有关您感兴趣的约束的信息，我或其他人可能能够为您提出一个不涉及蛮力枚举的更具体的解决方案。

于 2013-02-28T03:07:35.020 回答
1

即使 1000 个 k 大小的集合中只有 1 个符合您的条件，那仍然有太多组合无法测试。我相信运行时会随着 nCk（n 选择 k）而扩展，其中 n 是未排序列表的大小。Andrew Mao 的回答与这个值有链接。10^28/1000 仍然是 10^25。即使每秒进行 1000 次测试，这仍然是 10^22 秒。=10^14 年。

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

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

于 2013-02-28T03:37:05.667 回答
1

如果您想要的小子集的属性（称为它P）相当普遍，那么概率方法可能会很好用：

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

注意初始排序是O(n log n). 步骤 4 中隐含的二分查找是O(log n).

显然，如果P这种情况非常罕见，以至于随机投篮不太可能得到匹配，那么这对你没有好处。

于 2013-02-28T03:40:19.923 回答
0

这是执行您所说的大致方法。

首先，对列表进行排序。然后，考虑一些长度为 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

基本上，这意味着您不再需要检查 5 元素组合(1, ..., n+1)是否在 中找到令人满意的分配(1, ..., n)，因为任何具有最大索引的令人满意的分配n+1将具有更大的总和，并且您可以在该集合之后停止。但是，没有简单的方法可以循环遍历(1, ..., n)while 的 5 个组合，以保证总和始终在增加，但至少您可以在找到满意的集合后停止检查 some n。

于 2013-02-28T03:43:35.177 回答
0

这看起来是 map-reduce ( http://en.wikipedia.org/wiki/MapReduce )的完美候选。如果您知道任何巧妙地划分它们的方法，以便通过的候选者平等地出现在每个节点中，那么您可能会获得很大的吞吐量。

可能真的不需要完整的排序，因为 map 阶段可以处理它。然后，每个节点都可以根据 k 元组验证条件并将结果输出到一个文件中，该文件可以稍后聚合/减少。

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

于 2013-02-28T03:58:59.877 回答