所有可能的方式，其中K個項目可以排列在N個插槽中

我正在尋找一種算法來查找K個項目的所有K個組合。所有可能的方式，其中K個項目可以排列在N個插槽中

實施例：

的K值是[R，B] & N爲2，所以我得到{RR，RB，BR，BB} 2 * 2 = 4種方式

的K值是[R， B] & N是3所以我得到{RRR，RRB，RBB，RBR，BRR，BRB，BBR，BBB} 2 * 2 * 2 = 8種方式

我需要找出一般算法來找到所有可能的可以將K個項目排列在N個插槽中的方式。（重複是允許的）

另一個例子是：

的K值是[R，G，B] & N是5，所以我需要找到3^5 = 81個的組合。

來源

2012-07-06 Vivek

這是**的變體**，因爲順序是相關的。您的問題與N位數字的K數字一一對應。 – 2012-07-06 11:00:30

我同意@MarkoTopolnik。但是，這幾乎是一個常見問題，所以我投票結束。 – 2012-07-06 11:07:02

[重複變異的代碼（combinatorics）的可能的重複？]（http://stackoverflow.com/questions/2366074/code-for-variations-with-repetition-combinatorics） – 2012-07-06 11:07:59

此問題非常適合遞歸解決方案。

通常情況下的解決方案是通過採用N - 1的解決方案，然後將每個設置的元素依次添加到結果中形成的。在僞代碼：

f(options, 0) = [] 
f(options, n) = options foreach o => o ++ f(options, n-1)

這可能遞歸用Java來實現，但你會遇到堆棧溢出錯誤爲n中等大值;我也懷疑JIT編譯器在優化遞歸算法方面效率不高，因此性能會受到影響。

但是，遞歸算法總是可以轉換成等效的循環。在這種情況下，它可能看起來像：

List<String> results = new ArrayList<String>(); 
results.add(""); // Seed it for the base case n=0 
for (int i = 0; i < n; i ++) { 
    List<String> previousResults = results; 
    results = new ArrayList<String>(); 
    for (String s : options) { 
     for (String base : previousResults) { 
      results.add(s + base); 
     } 
    } 
} 
return results;

這種工作方式類似於遞歸方法 - 在每次迭代它「拯救」目前的進度（即，n-1的結果）previousResults，然後（我希望！）只是依次迭代選項，以獲得將結果添加到前一結果的結果。

看到通過任何自動遞歸迭代算法傳遞遞歸解決方案的效果，並將可讀性和性能與此手工創建的算法進行比較，將會很有趣。這留給讀者作爲練習。

來源

2012-07-06 11:09:47

我將使用基數爲k的N位計數器。例如：K = 3，N = 5

(0,0,0,0,0) 
(0,0,0,0,1), 
.... 
(2,2,2,2,2)

實現這樣的計數器是容易的，只要保持大小爲n + 1，將所有元素的數組tozero起初，每次增加最新元件，並且如果它會超過k-1，增加下一個鄰居（直到鄰居超過k-1）。當n + 1元素設置爲1時動作終止。

如果您嘗試過並且無法做到這一點，請通過評論告訴它。

來源

2012-07-06 11:20:27

所有可能的方式，其中K個項目可以排列在N個插槽中

回答

相關問題