python pyplot 按最小和生成整數的組合




title plt (3)

我的問題源於生成一個非常大的素數排序列表的唯一組合選擇5,但我需要的組合返回,以便最小的總和組合返回首先。 Python的itertools.combinations()函數返回數字,增加最後一個,直到它達到可迭代對象的末尾,然後增加下一個,等等。這是不適合我的項目,因為總和將繼續增加,直到達到我素數集的最後一個元素,在這一點上,總和會下降,然後再增加。

例如,如果我有一{2,3,5,7,11,13,17,19,23,29}素數{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個整數的元組。 而且,返回的元組中的每個元素必須是唯一的; 不能有重複的整數。 有任何想法嗎?


如果它可以幫助你 ,這裡是一個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 
        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;
}

我不確定這需要多少空間,所以最好先用一組較小的素數來嘗試。

  • 有一個數組/素數列表,按升序排序。

  • 保持索引五元組的優先級隊列,其中相應的素數之和作為鍵/權重/優先級/ whaddaycallit,初始填充權重2+3+5+7+11 = 28的五元組(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. 產生以前得到的五倍

不要產生組合和求和,而要反過來試一試 - 給定一個和數序列,為每個和產生組合:

# 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

這在性能上遠非理想,但在我的機器上還是相當快的。







primes