在C++中計算具有不同列數的不同數字組合？

我真的很感激，如果有人能指出我對這個問題的正確方向。我試圖找到各種不同數字的不同組合（C++中）。例如考慮數2：在C++中計算具有不同列數的不同數字組合？

兩列：

2 = {2,0} {0,2} {1,1}

三列：

2 = {0，0，2} {0，2,0} {2，0,0} {1，1，0} {0，1,1} {1，0,1}

四列：

2 = {0，0，0，2} {0，0，2,0} {0，2，0，0} {2，0，0，0} {1，1，0，0} {0，0，1，1} {0，1，1，0} {1，0，0，1} {1，0，1，0} {0,1,0,1}

在此先感謝！

來源

2013-10-12 godzilla

這只是這麼多大學的功課，我不能強迫自己認爲並非如此。 – Behrooz

你可能會驚訝地聽到這個，但這不是一個大學問題 – godzilla

無論如何，請閱讀http://en.wikipedia.org/wiki/Binomial_coefficient。它可能有幫助 – Behrooz

這裏是我的嘗試：

void combinations(int n, int columns, std::vector<int>& soFar) 
{ 
    if (columns == 1) 
    { 
     for (auto e : soFar) 
      std::cout << e << " "; 
     std::cout << n << '\n'; 
     return; 
    } 

    for (int i = 0; i <= n; ++i) 
    { 
     soFar.push_back(i); 
     combinations(n - i, columns - 1, soFar); 
     soFar.pop_back(); 
    } 
} 

void combinations(int n, int columns) 
{ 
    std::vector<int> soFar; 
    combinations(n, columns, soFar); 
}

基本上，你不斷分裂成數兩個子部分，直到你達到你的深度限制（列在你的案件的數量）。
要繼續打印之前的數字，我將它們存儲在soFar矢量中，並相應地推入並彈出它們。

這裏的輸出combinations(2, 4)：

來源

2013-10-13 19:10:12

你知道我在驚訝地看着這個，我已經寫了自己的代碼，但是沒有類似的效果，所以我感到非常驚訝 – godzilla

考慮分拆的問題分爲兩個子問題：

1）發現，添加到您的號號碼的所有組合：

即：2列的情況下爲「3」：（2,1）和（3,0）

2）置換你已經找到了所有組合：

即：（2,1） - >（2,1），（1,2）和（3,0 ） - >（3,0），（0,3）

對於部分1），你會得到很大的數字和多列的問題，說5 4列（我知道，他們是深奧巨大的數字）：

5 = 4 + 1

5 = 3 + 2

5 = 3 + 1 + 1

5 = 2 + 1 + 1 + 1

5 = 1 + 1 + 1 + 1 + 1

如果仔細觀察，可能會發生遞歸。如在，對於5 = 3 + 2：找到組合3和組合2等等...直到你達到1

只要你說遞歸，樹結構開始聽起來很有趣。這就是我如何處理這個問題。

來源

2013-10-12 17:45:25 TheSeamau5

有趣的是，什麼讓這個困難是想添加任意數量的列 – godzilla

這是一個簡單的組合問題。如果你有m列，那麼你在列之間有m-1個分隔符。用數字n，你想要所有的方式來訂購m-1分頻器和n個元件。例如，對於n = 5和m = 3，一種可能的排列是xx，x，xx - 並且您正在查看7個選擇2.

所以一般的解決方案是m + n-1選擇m-1 ，或等價地，m + n-1選擇n。

x選擇y的公式是x！/[y！！*（X-Y）]

來源

2013-10-12 17:46:12 Zook

你能告訴我一個例子嗎？ – godzilla

我剛剛測試過這個，它不完全是我想要的 – godzilla

在C++中計算具有不同列數的不同數字組合？

回答

相關問題