1

如果有人能指出这个问题的正确方向，我将不胜感激。我试图找到各种数字的所有不同组合，每个数字都有不同的列数（在 C++ 中）。例如考虑数字 2：

两列：

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 }

提前致谢！

4

3 回答 3

1

这是我的尝试：

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)：

0 0 0 2
0 0 1 1
0 0 2 0
0 1 0 1
0 1 1 0
0 2 0 0
1 0 0 1
1 0 1 0
1 1 0 0
2 0 0 0
于 2013-10-13T19:10:12.423 回答
0

这是一个直接的组合问题。如果您有 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！/[耶！* (xy)!]

于 2013-10-12T17:46:12.397 回答
0

考虑将问题拆分为两个子问题：

1) 找出所有加到你的数字上的数字组合：

即：“3”的 2 列大小写：(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-12T17:45:25.767 回答