生成限量用品的組合/數字列表

Question

假設我有1個紅色球，1個藍色球，2個黃色球和3個綠色球，共計7個球。

我想從七人組中選擇三個球。我可以做多少種方法？

當我手動計算時，我有11個組合/套。即123 124 133 134 144 233 234 244 334 344 444

什麼是生成和顯示所有這些組合/集合的有效方法？

需要注意的是獨特應用，所以(yellow, red, yellow) = (yellow, yellow, red)

Answer 1

雖然第二，但我建議一個生成函數的方法。

• 的紅球的數量可以是：0,1
• 藍色球的數量可以是：0,1
• 黃色球的數量可以是：0,1,2
• 綠球的數量可以是： 0,1,2,3

因此要展開下面的多項式

(1 + x) * (1 + x) * (1 + x + x^2) * (1 + x + x^2 + x^3) 

並查看x^3的係數，因爲您要共計3球。

這將給你一些方法來做到這一點，從每個括號內的表達式中取一項來獲得係數的方法會告訴你如何進行組合。這是有效的，因爲選擇0或1紅色球分別與第一項(1 + x)分別選擇1或x相同，並且類似地選擇i綠色球意味着從上一項選擇術語x^i。然後選擇的總球數是指數的總和。既然你想3球，你應該看看的x^3係數時，這個多項式擴展：

1 + 4x + 8x^2 + 11x^3 + 11x^4 + 8x^5 + 4x^6 + x^7 

因此有從給定3球11可能的組合。

要重複的可能性，你可以選擇從表達式項依次是：

int count = 0; 
for (int r=0; r<=1 && r<=3; ++r) { 
    for (int b=0; b<=1 && r+b<=3; ++b) { 
     for (int y=0; y<=2 && r+b+y<=3 ; ++y) { 
      for (int g=0; g<=3 && r+b+y+g==3; ++g) { 
       count++; 
       printf(" red: %d\n blue: %d\nyellow: %d\n green: %d",r,b,y,g); 
      } 
     } 
    } 
} 
return count; 

前兩個for環路（r<=3和r+b<=3）第二個條件是不必要在這個例子中，但我留下來說明如何將問題推廣。

Answer 2

generate_combinations(a1, a2, a3, a4, c1, c2, c3, c4) 
1. if a1 + a2 + a3 + a4 = 3 then print (a1, a2, a3, a4) 
2. else then 
3. if c1 > 0 then generate_combinations(a1+1, a2, a3, a4, c1-1, c2, c3, c4) 
4. if c2 > 0 then generate_combinations(a1, a2+1, a3, a4, c1, c2-1, c3, c4) 
5. if c3 > 0 then generate_combinations(a1, a2, a3+1, a4, c1, c2, c3-1, c4) 
6. if c4 > 0 then generate_combinations(a1, a2, a3, a4+1, c1, c2, c3, c4-1) 

或者類似的東西。這不會重複，但是...我想你可以添加更多的邏輯來過濾出來，但是。也許後處理？

一些澄清：這通過保持（1）手中的球和（2）袋中的球的計數。它確保手+袋=每種顏色的原始。用最初空着的手來稱呼它，它會在你手中有三個球的方式打印。

如果您確實希望確保該算法僅提供唯一的算法（而不是將這與算法結合使用以從列表中刪除重複項），則可以確保不添加任何如果你已經添加了任何高階球（即，如果a2> 0和a1 = 0，那麼你不需要添加任何紅色）。