X分爲N堆棧的每種可能的組合

我確信這個問題有一個正式的名稱，並且知道該名稱可能會幫助我找到解決方案，但我不知道它，並且爲Google解釋問題我到Knapsack Problem，這是不一樣的事情。X分爲N堆棧的每種可能的組合

我想取一些值X並找到將該值拆分爲N個整數整數的可能組合。

如果我的措辭是混亂的，這裏是X = 4的示例，N = 3

Stack -> 1 | 2 | 3 | 
---------------------- 
#1-----> 4 | 0 | 0 | 
---------------------- 
#2-----> 3 | 1 | 0 | 
---------------------- 
#3-----> 2 | 1 | 1 | 
---------------------- 
#4-----> 2 | 2 | 0 |

複製是可以接受的，因爲它很容易除去，但最好它不會被計算。解決問題的算法是完美的，但即使發現問題有名稱也會使研究更容易。謝謝。

來源

2012-06-13 Tyrsius

所以，你要的是添加到'x'的完全是一個總和'N'號碼？你不希望包含少於'n'部分的組合/排列？零是一個有效的部分。零件的順序是否重要？不同順序的相同部分是否重複？ – Jodrell

你只想要組合的數量，還是要打印所有的組合？ –

我認爲這可能類似於你正在尋找的東西。 http://stackoverflow.com/questions/2593781/print-all-ways-to-sum-n-integers-so-that-they-total-a-given-sum – corn3lius

這是user434507在C＃的答案：

class Program 
{ 
    static void Main(string[] args) 
    { 
     var v = Partitions(5, 3, 5); 

     for (int i = 0; i < v.Count; i++) 
     { 
      for (int x = 0; x < v[i].Count; x++) 
       Console.Write(v[i][x] + " "); 
      Console.WriteLine(); 
     } 
    } 

    static private List<List<int>> Partitions(int total, int stacks, int max) 
    { 
     List<List<int>> partitions = new List<List<int>>(); 

     if (total <= 1 || stacks == 1) 
     { 
      if (total <= max) 
      { 
       partitions.Add(new List<int>()); 
       partitions[0].Add(total); 
      } 

      return partitions; 
     } 
     for (int y = Math.Min(total, max); y >= 1; y--) 
     { 
      var w = Partitions(total - y, stacks - 1, y); 
      for (int i = 0; i < w.Count; i++) 
      { 
       w[i].Add(y); 
       partitions.Add(w[i]); 
      } 
     } 

     return partitions; 
    } 
}

來源

2012-06-13 18:02:35

請看我的答案。 – Tyrsius

用有意義的變量名稱更新 –

這似乎這樣的伎倆：

vector<vector<int> > partitions(int X, int N, int Y) 
{ 
    vector<vector<int> > v; 
    if(X<=1 || N==1) 
    { 
     if(X<=Y) 
     { 
      v.resize(1); 
      v[0].push_back(X); 
     } 
     return v; 
    } 
    for(int y=min(X, Y); y>=1; y--) 
    { 
     vector<vector<int> > w = partitions(X-y, N-1, y); 
     for(int i=0; i<w.size(); i++) 
     { 
      w[i].push_back(y); 
      v.push_back(w[i]); 
     } 
    } 
    return v; 


    } 

int main() 
{ 
    vector<vector<int> > v = partitions(5, 3, 5); 
    int i; 
    for(i=0; i<v.size(); i++) 
    { 
     int x; 
     for(x=0; x<v[i].size(); x++) 
      printf("%d ", v[i][x]); 
     printf("\n"); 
    } 
    return 0; 
}

來源

2012-06-13 17:37:23 user434507

我相信這很棒，但我不知道它是什麼語言，我無法理解這一切。「Vector」是一種數組嗎？ 'push_back'是做什麼的？ – Tyrsius

這是C++ ...你想要什麼語言你的答案？ – user434507

它是C++，矢量是動態數組的STL實現。如果可以的話，C＃＃ –

這些其實都是integer partitions爲刪除答案的言論。使用Mathematica：

IntegerPartitions[4, 3] // PadRight //Grid

輸出：

我無法找到一個C＃實現，但這裏有幾個相關問題：

Elegant Python code for Integer Partitioning

Integer Partition in Java

Algorithm for generating integer partitions

谷歌點擊：

Integer Partition Algorithm by Jerome Kelleher

Integer Partition Algorithm by Daniel Scocco

Fast Algorithms for Generating Integer Partitions（PDF）（看起來重型）

Stony Brook Algorithm Repository - Partitions

來源

2012-06-13 17:42:33

@MrWizard感謝您的名字，這將有所幫助。我很想知道這是如何產生的。這些鏈接似乎沒有任何代碼顯示正在使用的算法。 – Tyrsius

@MrWizard，過早發佈了第二個，謝謝你的代碼鏈接！ – Tyrsius

@Tyrsius我加入更多，因爲我找到他們，繼續觀看。 –

X分爲N堆棧的每種可能的組合

回答

相關問題