X的每个可能组合分成N个堆栈
我确信这个问题有一个正式的名称,并且知道这个免费精选名字大全可能会帮助我找到解决方案,但我不知道,并且谷歌的问题一直指向我背包问题 ,这是不一样的事情。
我想取一些值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 |
复制是可以接受的,因为它很容易删除,但理想情况下不会计算。 解决问题的算法将是完美的,但即使找出问题的名称也会使研究更容易。 谢谢。
这是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> Partitions(int total, int stacks, int max) { List> partitions = new List>(); if (total <= 1 || stacks == 1) { if (total <= max) { partitions.Add(new List ()); 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; } }
这些实际上是整数分区作为删除的答案备注。 使用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算法库 – 分区
这似乎可以解决问题:
上述就是C#学习教程:X的每个可能组合分成N个堆栈分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!
vector > partitions(int X, int N, int Y) { vector > 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 > w = partitions(Xy, N-1, y); for(int i=0; i > v = partitions(5, 3, 5); int i; for(i=0; i
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/1013438.html