给定以下降序唯一数字列表 (3,2,1),我希望生成所有由这些数字组成的序列,直到最大总和。
假设总和应低于 10。那么我所追求的序列是:
3 3 3
3 3 2 1
3 3 2
3 3 1 1 1
3 3 1 1
3 3 1
3 3
3 2 2 2
3 2 2 1 1
3 2 2 1
3 2 2
3 2 1 1 1 1
3 2 1 1 1
3 2 1 1
3 2 1
3 2
3 1 1 1 1 1 1
3 1 1 1 1 1
3 1 1 1 1
3 1 1 1
3 1 1
3 1
3
2 2 2 2 1
2 2 2 2
2 2 2 1 1 1
2 2 2 1 1
2 2 2 1
2 2 2
2 2 1 1 1 1 1
2 2 1 1 1 1
2 2 1 1 1
2 2 1 1
2 2 1
2 2
2 1 1 1 1 1 1 1
2 1 1 1 1 1 1
2 1 1 1 1 1
2 1 1 1 1
2 1 1 1
2 1 1
2 1
2
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1
1 1
1
我确信有一种“标准”方法可以生成它。
我想过使用 linq,但无法弄清楚。 另外,我正在尝试一种基于堆栈的方法,但我仍然没有成功。
有什么想法吗?
最佳答案
我认为这是最容易递归编写的,纯 LINQ 不太适合。所以最好将其实现为一个普通的递归函数。将最大总数中剩余的数量作为参数传递,每次添加 en 元素时,递归调用该函数,适当减少总数:
IEnumerable<IEnumerable<int>> sequences(IEnumerable<int> set, int maxTotal)
{
foreach (int i in set.Where(x => x <= maxTotal))
{
yield return new int[] { i };
foreach (var s in sequences(set.Where(x => x <= i), maxTotal - i))
yield return (new int[] { i }).Concat(s);
}
}
void Run()
{
foreach (var z in sequences(new int[] { 3, 2, 1 }, 10))
{
Console.WriteLine(
string.Join(" ", z.Select(x => x.ToString()).ToArray())
);
}
}
结果:
3
3 3
3 3 3
3 3 3 1
3 3 2
3 3 2 2
3 3 2 1
3 3 2 1 1
3 3 1
3 3 1 1
3 3 1 1 1
...
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
请注意,这不是最有效的解决方案。
关于c# - 尝试生成指定数字的所有序列,直到达到最大总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2594444/