程序以產生k個的NCK組合從1變化至n

Question

My功能定義如下所示 nxt_comb[] = Combination(comb[1:k],n)

該函數應該給它而來的輸入組合comb（數組）之後的下一個組合。 comb的n元素取值從1到n。

實施例：

• 如果功能被稱爲a = Combination([1,3,4,6],8)，然後a = [1,3,4,7]
• 如果功能被稱爲a = Combination([1,3,4,8],8)，然後a = [1,3,5,6]
• 如果功能被稱爲a = Combination([1,3,7,8],8)，然後a = [1,4,5,6]
• 如果功能被稱爲a = Combination([3,6,7,8],8)，然後a = [4,5,6,7]

輸入組合不會是最後一個組合。也就是說，在上述情況下，輸入將永遠不會是[5,6,7,8]。

另外，如果輸入全爲零，則函數必須輸出第一個組合，即[1,2,....,k]。

編輯：我在找的是邏輯。實現可以使用C/C++或MATLAB。

Answer 1

撇開最後一個要求有關與全0，這是一個微不足道的額外的檢查開始，該算法是：

1. 通過反向搜索，找到最大的i，使得基於1 comb[i]<i+n-k（使用索引;如果你使用C，則調整）。如果你找不到一個，你就是最後一個組合。

2. 增量梳[I]，然後從j = i+1工作到k，設置comb[j]到comb[j-i]+1