C＃算法 - 列出編號的所有排列

這是我之前發佈的一個問題（C# algorithm - find least number of objects necessary）的後續行爲，但有點不同。C＃算法 - 列出編號的所有排列

鑑於我有以下代碼：

var max = 80; 
var list = new[]{10,20,30,40,50, 60);

我要生成一個包含所有可能的組合，我可以使用這些數字在列表中獲取到最大數目的陣列。

陣列將包含，{40,40}，{50,30}，{40,30，10}等...

來源

2009-12-21 Paul

這是什麼問題？：P – 2009-12-21 21:39:03

鑑於您允許重複數字，您是否保證列表中的所有數字均大於零？ – 2009-12-21 21:39:56

看起來像F的工作＃ – Manu 2009-12-21 21:41:17

簡易方法是簡單地產生可能的數字的每一個組合，並且看他們是否加起來到目標號碼。

不用說，這具有可怕的時間複雜性。但它爲小列表做了工作。

編輯：其實，如果你允許重複的數字，這是行不通的。另一種算法（允許重複但不是任何否定）是基本上將列表中的最高數加起來，然後如果超過目標則回溯。

來源

2009-12-21 21:43:30

您需要按降序迭代所有數字。然後遞歸地在序列中添加每個下一個遞減數字。每次匹配時，請注意組合，彈出和繼續。當您的暫定總和將您帶到最大變量時，從函數中彈出到堆棧中的下一個函數。如果尚未達到最大值，則連續向下添加下一個數字。通過這種方式，你將覆蓋可能的序列，沒有重複（除非在給定集合中有重複，在這種情況下，你會想要重複）。實際上它不會太多代碼。

來源

2009-12-21 21:47:42

好摘要。儘管從保羅的例子來看，似乎重複是允許的，不管重複是否在集合中。 – 2009-12-21 21:50:22

雖然調整這個算法以允許這樣做是微不足道的 - 只是從當前數字開始遞歸，而不是從下一個較低的數字開始。 +1。 – 2009-12-21 21:51:37

oi，是的！然後，您總是需要將當前操作的編號包含到下一個遞歸函數調用中。所以，仍然是簡單的代碼，但是，對於大集合來說，好主，這將是可怕的！對於一個非常大的集合，需要一些花哨的數學。別看我！ – 2009-12-21 21:55:03

C＃算法 - 列出編號的所有排列

回答

相關問題