通過最小總和生成整數組合

Question

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

舉例來說，如果我有一小素數{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個元素，這意味着簡單地生成所有組合並對它們進行排序是難以置信的不可行的，因爲它需要每個5個整數的83,325,000,291,662,500,020,000個元組的空間。此外，返回的組合元組中的每個元素必須是唯一的;不能有重複的整數。有任何想法嗎？

Answer 1

代替生成組合和總結他們，嘗試用另一種方式圓 - 給定和的序列，每個總和產生的組合：

# 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 

這是很不理想在性能方面，但仍在我的機器上相當快。

Answer 2

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

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

• 保留索引-五元組的一個優先級隊列，與相應的素數作爲密鑰/重量/優先級/ whaddayacallit的總和，最初充滿重量2+3+5+7+11 = 28的五元組(0,1,2,3,4)。

• 雖然隊列不爲空，

  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. 產生之前得到五重

Answer 3

如果它可以幫助你，這裏是在C程序幾乎通過最小總和生成整數的組合。整數必須按升序排列。這種編程'從其他程序中this post繼承：

#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; 
}