X的每个可能组合分成N个堆栈

Question

我确信这个问题有一个正式的名称,并且知道这个名字可能会帮助我找到解决方案,但我不知道,并且谷歌的问题一直指向我背包问题,这是不一样的事情.

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

复制是可以接受的,因为它易于删除,但理想情况下不会计算.解决问题的算法将是完美的,但即使找出问题的名称也会使研究更容易.谢谢.

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算法库 - 分区

Answer 2

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