生成數字組合而不重複的算法

我在這裏查了幾乎所有類似的帖子，但我無法弄清楚我怎麼能做到我想要的。我試圖是給輸入在C程序，讓說，4號，程序返回下面的號碼數組：生成數字組合而不重複的算法

更清楚：如果輸入的數字是4則我想使用數字1-4並生成所有可能的數字組合（從1位數組合到4位數組合），無需重複數字。

我嘗試以下的代碼：

#include <stdio.h> 

/* Prints out a combination like {1, 2} */ 
void printc(int comb[], int k) { 
    printf("{"); 
    int i; 
    for (i = 0; i < k; ++i) 
     printf("%d, ", comb[i] + 1); 
    printf("\\b\\b}\\n"); 
} 


    int next_comb(int comb[], int k, int n) { 
    int i = k - 1; 
    ++comb[i]; 
    while ((i >= 0) && (comb[i] >= n - k + 1 + i)) { 
     --i; 
     ++comb[i]; 
    } 

    if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */ 
     return 0; /* No more combinations can be generated */ 

    /* comb now looks like (..., x, n, n, n, ..., n). 
    Turn it into (..., x, x + 1, x + 2, ...) */ 
    for (i = i + 1; i < k; ++i) 
     comb[i] = comb[i - 1] + 1; 

    return 1; 
} 

int main(int argc, char *argv[]) { 
    int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */ 
    int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */ 
    int comb[16]; /* comb[i] is the index of the i-th element in the 
      combination */ 

    /* Setup comb for the initial combination */ 
    int i; 
    for (i = 0; i < k; ++i) 
     comb[i] = i; 

    /* Print the first combination */ 
    printc(comb, k); 

    /* Generate and print all the other combinations */ 
    while (next_comb(comb, k, n)) 
     printc(comb, k); 

    return 0; 
}

上述程序輸出結果。我想以某種方式得到結果..但我不能，因爲上面的代碼以奇怪的方式打印結果。

來源

2013-04-26 Dchris

而你的問題是......？ – 2013-04-26 16:42:29

你正試圖展示原始輸入的某種排列？你的問題不是很清楚。 – 2013-04-26 16:49:57

我修正了輸出並添加了一個更好的解釋 – Dchris 2013-04-26 16:54:10

我們使用int來表示一個集合。對於第i位，如果它是1，那麼我在該集合中，反之亦然。

以一個例子：1010（2）= {4,2} 1111（2）= {4,3,2,1}

對於每一個將要考慮的元件，有兩種選擇：在或不在集合中。

所以，總共有2^n個不同的組合。在我的代碼中，我只是枚舉每個可能的int對應一個集合，並輸出相應的集合。

所以我們得到這個代碼：

for(int i=1;i<(1<<n);i++) 
{ 
    for(int j=0;j<n;j++) 
     if ((1<<j)&i) printf("%d",j+1); 
    puts(""); 
}

當n = 4，輸出：

如果你想輸出的答案給予的順序，才使他們的字符串，並把這些字符串在向量中進行排序。

如果n很大，可以使用bitset。但是，當n> 30時，它可能不會在幾小時內終止。所以int是高效的。

來源

2013-04-26 17:11:00 Sayakiss

爲了解決OP所具有的特定問題，這太棒了。我真的不確定它是否是標準便攜式的（我認爲是這樣，但需要稍微閱讀一下）。如果是這樣，它將適用於大於'（sizeof（int）* 8）-2'的數字，如果使用'unsigned int'，則可以擠出多餘的數據。如果需要更大的尺寸，可以很容易地加入一個帶有額外循環的字節數組。總而言之，一個很好的答案。 – WhozCraig 2013-04-26 17:23:18

我想爲算法的工作原理在頂部添加說明會很好。該算法生成（無序）集並用一組位表示它們。所以'{1,2,3,4} = 1111'和'{} = 0000'和'{1,3} = 1010'等等。它遍歷所有的比特集並且通過檢查該位是否「打開」（即'== 1），並打印出來（如果是這樣的話）。啊，我只是注意到它不打印空集，但可能或不可取。 – rliu 2013-04-26 18:05:53

啊，我搞砸了訂貨。它更像'{4,3,2,1} = 1111'（而不是'{1,2,3,4} = 1111'） – rliu 2013-04-26 18:12:21

這是一個程序，可以產生數字的組合。它用C寫成。但它可以用任何其他語言重寫。現在，只需編譯並嘗試！

#include <stdio.h> 
#include <stdlib.h> 
int v[100], stack[100]; 
int sp,i,n,g; 
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("running...\n"); 
sp=-1; 
while(1) { 
// stack ones until stack overflow 
    while(sp<n-1) { 
     sp=sp+1; 
     stack[sp]=1; 
     for (i=0 ; i<=sp ; i++) if (stack[i]==1) printf("v[%d]=%d ",i,v[i]); 
     printf("\n"); 
    } 
// 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; 
    } 
return 0; 
}

對於n = 4運行：

[[email protected] fin]$ ./comb 
Dimension of V:4 
V[0]=10 
V[1]=20 
V[2]=30 
V[3]=40 
running... 
v[0]=10 
v[0]=10 v[1]=20 
v[0]=10 v[1]=20 v[2]=30 
v[0]=10 v[1]=20 v[2]=30 v[3]=40 
v[0]=10 v[1]=20 v[3]=40 
v[0]=10 v[2]=30 
v[0]=10 v[2]=30 v[3]=40 
v[0]=10 v[3]=40 
v[1]=20 
v[1]=20 v[2]=30 
v[1]=20 v[2]=30 v[3]=40 
v[1]=20 v[3]=40 
v[2]=30 
v[2]=30 v[3]=40 
v[3]=40

來源

2014-06-17 15:50:03

生成數字組合而不重複的算法

回答

相關問題