遍歷所有可能的組合

Question

我的目標是遍歷給定數量的1和0的所有組合。再說了，如果我給5號，這將是一個足夠快的方式列出

1110100100， 1011000101等

我試圖（5 1和5 0的每個不同組合）避免遍歷所有可能的排列，並檢查5 1是否存在，因爲2^n遠大於（n選擇n/2）。謝謝。

Answer 1

你可以改變這個問題。如果您修復了1（反之亦然），那麼這只是您將0的位置放在哪裏的問題。對於5 1 s，有5 + 1個垃圾箱，並且您希望將5個元素（0 s）放入垃圾箱中。

這可以通過每個bin的遞歸和每個bin的循環來解決（把0 ... reaming元素放在bin中 - 除了最後一個bin，你必須放置所有remaning元素）。

Answer 2

想想它的另一種方法是作爲string permutation question的一個變體 - 只需構建一個長度爲2n的向量（例如111000），然後使用相同的算法進行字符串置換以生成結果。

請注意，天真的算法會打印重複的結果。然而，該算法可以很容易地適應忽略這樣的重複，通過在遞歸函數中保留布爾數組來保持爲特定位設置的值。