将 X 的所有可能组合分成 N 堆

Question

我很确定这个问题有一个正式的名称，了解这个名称可能会帮助我找到解决方案，但我不知道它，而且用谷歌搜索时，描述这个问题总是指向0/1 背包问题，这其实与我的问题不同。

我想要取一个值 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 |

重复是可以接受的，因为很容易删除，但理想情况下不应计算。解决此问题的算法将是完美的，但即使找出问题的名称也会使研究更加容易。谢谢。

- Kyeotic

---

所以，你想要 n 个数字，它们的总和恰好为 x？你不想包括少于 n 部分的组合/排列？零是否是有效部分？部分的顺序是否重要？同样的部分以不同的顺序是否会重复？ - Jodrell

你只需要组合的数量，还是想要打印出所有的组合？ - Aasmund Eldhuset

我认为这可能与您正在寻找的内容相似。http://stackoverflow.com/questions/2593781/print-all-ways-to-sum-n-integers-so-that-they-total-a-given-sum - corn3lius

如果你再仔细想一下，实际上这就是NP背包问题。只不过你的背包里，我猜测，装着所有小于x且大于0的整数，并且你只想要长度为n的组合。 - Jodrell

@AasmundEldhuset 打印所有组合。 - Kyeotic

Answer 1

这些实际上是整数分割，正如被删除的回答所指出的。使用Mathematica：

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

输出：

4   0   0
3   1   0
2   2   0
2   1   1

---

我找不到C#的实现，但这里有几个相关的问题：

Python中优雅的整数划分代码

Java中的整数划分

生成整数划分的算法

---

谷歌搜索结果：

Jerome Kelleher的整数划分算法

Daniel Scocco的整数划分算法

生成整数划分的快速算法（PDF）（看起来很复杂）

Stony Brook算法仓库-划分

- Mr.Wizard

---

@MrWizard感谢您提供的名称，这很有帮助。我想知道这是如何生成的。链接中似乎没有任何代码显示所使用的算法。 - Kyeotic

@MrWizard，发了一秒钟太早了，感谢您提供的代码链接！ - Kyeotic

@Tyrsius 我会不断添加，你继续关注。 - Mr.Wizard

太好了，一旦我编写完C#方法，我就会发布它。 - Kyeotic

@Tyrsius 我找到了另一个链接，我想要加入它；它链接到几个不同的实现并给出了它们的评级。 - Mr.Wizard

Answer 2

这似乎是解决的方法：

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;
}

- Eugene Smith

---

我相信这很棒，但我不知道它是用什么语言编写的，而且我无法理解它。Vector是一种数组类型吗？push_back是什么意思？ - Kyeotic

这是C++...你希望用哪种语言回答？ - Eugene Smith

这是C++，vector是动态数组的STL实现。 - Alex Peck

如果可以的话，我会用C#，但我不介意学习这里发生了什么。 - Kyeotic

我对此不了解足够的C#。向量只是动态数组，而push_back将元素插入到数组的末尾。函数partitions（X，N，Y）返回最多使用N个堆且没有堆大于Y的可能分区列表。 - Eugene Smith

Answer 3

这是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;
    }
}

- Alex Peck

---

已更新为有意义的变量名称 - Alex Peck