3

我的问题源于生成一个非常大的素数排序列表的唯一组合选择 5，但我需要返回组合，以便首先返回总和最小的组合。pythonitertools.combinations()函数返回数字，增加最后一个直到它到达可迭代对象的末尾，然后再增加下一个，等等。这不适合我的项目，因为总和将继续增加，直到它到达我集合的最后一个元素质数，此时总和将下降，然后再次增加。

例如，如果我有一小组 primes {2,3,5,7,11,13,17,19,23,29}，我需要按以下顺序返回组合：

    (2, 3, 5, 7, 11)    sum = 28
    (2, 3, 5, 7, 13)    sum = 30
    (2, 3, 5, 7, 17)    sum = 34
    (2, 3, 5, 11, 13)   sum = 34
    (2, 3, 5, 7, 19)    sum = 36
    (2, 3, 7, 11, 13)   sum = 36
    (2, 3, 5, 11, 17)   sum = 38
    (2, 5, 7, 11, 13)   sum = 38
    (3, 5, 7, 11, 13)   sum = 39
    (2, 3, 5, 7, 23)    sum = 40
    (2, 3, 5, 11, 19)   sum = 40
    (2, 3, 5, 13, 17)   sum = 40
    (2, 3, 7, 11, 17)   sum = 40
    (2, 3, 5, 13, 19)   sum = 42
    (2, 3, 7, 11, 19)   sum = 42
    (2, 3, 7, 13, 17)   sum = 42
    (2, 5, 7, 11, 17)   sum = 42
    ...

两个总和相同的集合的顺序无关紧要，只要生成器在总和较小的集合之前不返回总和较大的集合即可。我正在使用的素数集包含大约 100,000 个元素，这意味着简单地生成所有组合并对它们进行排序是非常不可行的，因为它需要 83,325,000,291,662,500,020,000 个元组的空间，每个元组有 5 个整数。此外，返回的组合元组中的每个元素都必须是唯一的；不能有重复的整数。有任何想法吗？

4

3 回答 3

2

Instead of generating combinations and summing them, try it the other way round - given a sequence of sums, generate combinations for each sum:

# some primes for tesing
primes = [2]
x = 3
while x < 100000:
    if all(x % p for p in primes):
        primes.append(x)
    x += 2

# main code

def find(tsum, tlen):

    def _find(tsum, tlen, path, idx):
        if tlen <= 0:
            if tsum == 0:
                yield path
            return
        while True:
            p = primes[idx]
            if p > tsum:
                return
            for f in _find(tsum - p, tlen - 1, path + [p], idx + 1):
                yield f
            idx += 1

    return _find(tsum, tlen, [], 0)

for s in range(1001, 1002): # just for testing, should be range(28, max possible sum)
    for comb in find(s, 5):
        print s, comb

This is far from ideal in terms of performance, but still quite fast on my machine.

于 2013-05-28T16:43:35.257 回答
1

如果它可以帮助你，这里有一个 C 语言程序，它几乎可以通过最小和生成整数组合。整数必须按升序给出。这个程序是从这篇文章中的另一个程序继承而来的：

#include <stdio.h>
#include <stdlib.h>
int v[100], stack[100];
int sp,i,j,k,n,g,s;
int main()
{
    printf("Dimension of V:");
    scanf( "%d",&n);
    //Input numbers
    for (i=0 ; i<n ; i++) {
        printf("V[%d]=",i);
        scanf( "%d",&g);
        v[i]=g;
    }
    printf("subset number:");
    scanf( "%d",&k);
    printf("running...\n");
    j=0;
    s=0;
    sp=-1;
    while(1) {
        // stack ones until stack overflow
        while(sp<n-1 && j<k && n-sp>k-j)  {
            j=j+1;
            sp=sp+1;
            stack[sp]=1;
            s=s+v[sp];
            if(j==k) {
                for (i=0 ; i<=sp ; i++) if (stack[i]==1) printf("%2d ",v[i]);
                printf("sum=%d\n",s);
            }
        }
        // unstack all the zeros until top of stack is equal one
        while (stack[sp]==0 && sp>=0) sp=sp-1;
        // if Bottom of stack is reached then stop
        if (sp<0) break;
        // set top of stack from one to zero
        stack[sp]=0;
        s=s-v[sp];
        j=j-1;
    }
    return 0;
}
于 2014-11-29T20:28:43.510 回答
1

我不确定这需要多少空间，所以最好先用一组较小的素数尝试一下。

  • 有一个数组/素数列表，按升序排序。

  • 保留一个索引五元组的优先级队列，以对应的素数之和作为键/权重/优先级/whaddayacallit，最初用(0,1,2,3,4)权重的五元组填充2+3+5+7+11 = 28。

  • 虽然队列不为空，

    1. 从队列中获取总和最小的五元组，比如说(a, b, c, d, e, f)（当然，删除它）。

    2. 将它的直接后继插入队列，后继是那些

      • (a+1,b,c,d,e)
      • (a,b+1,c,d,e)
      • (a,b,c+1,d,e)
      • (a,b,c,d+1,e)
      • (a,b,c,d,e+1)

      它们是严格升序的，并且最后一个组件小于素数列表的长度

    3. 产生先前得到的五元组
于 2013-05-28T20:54:22.700 回答