c# - 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

这些实际上是整数分区作为删除答案的备注。使用数学：

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

这似乎可以解决问题：

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

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