X 的每个可能组合都拆分为 N 个堆栈
本文关键字:拆分 堆栈 组合 | 更新日期: 2023-09-27 18:37:16
我相信这个问题有一个正式的名称,知道这个名字可能会帮助我找到解决方案,但我不知道,谷歌的问题措辞一直把我指向背包问题,这不是一回事。
我想取一些值 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 |
重复是可以接受的,因为它很容易删除,但理想情况下不会计算。解决问题的算法将是完美的,但即使找出问题有一个名字也会使研究更容易。谢谢。
这些实际上是整数分区,作为已删除的答案备注。 使用 Mathematica:
IntegerPartitions[4, 3] // PadRight //Grid
输出:
4 0 0
3 1 0
2 2 0
2 1 1
我找不到 C# 实现,但这里有几个相关问题:
用于整数分区的优雅 Python 代码
Java 中的整数分区
生成整数分区的算法
谷歌点击:
Integer Partition Algorithm by Jerome Kelleher
Integer Partition Algorithm by Daniel Scocco
用于生成整数分区的快速算法 (PDF) (看起来很繁重)
石溪算法存储库 - 分区
这似乎可以解决问题:
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;
}
这是 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;
}
}