试图生成指定号码的所有序列长达最大总和
https://stackoverflow.com/questions/2594444
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
鉴于降序唯一号码的以下列表（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是不是伟大的。因此，这可能是最好的实现这个作为一个普通的递归函数。作为参数传递你已经从你的最大总并且每次添加恩元剩余时间量，递归调用的功能，适当地降低总：
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
请注意，这不是最有效的解决方案。
其他提示
在我看来，认为“最容易”（如果不是最有效的），这样做的方式是只把你的号码组，并利用其所有的排列，然后过滤掉，其和上述的那些截止点。
我不知道这是否是“标准”本身，而是它的不寻常开始在底部和工作了。
有使1 1种方式。
有2点的方法，使2，分为3类：开始那些具有1，开始用2的那些，以及那些开始用3.课程的最后一类是空
要计数使n的方式，可考虑的方法N-1从1开始，使得N-2开始与2或1的方法，以及制备N-3开始具有3,2的方式，或1。
这似乎是你感兴趣的分区，带着几分扭曲。这个函数的伎俩。基本上，不断增加数量的栈，而它们的总和是小于目标总和，那么在每个步骤打印堆栈。
class Program
{
static void Main()
{
GeneratePossibilites(new int[] {3, 2, 1}, 10, 0, new List<int>());
}
static void GeneratePossibilites(int[] array, int maxSum, int crSum, List<int> stack)
{
for (int i = 0; i < stack.Count; ++i )
Console.Write(array[ stack[i] ].ToString() + " ");
int start = 0;
if (stack.Count > 0)
{
start = stack[stack.Count - 1];
Console.WriteLine();
}
for (int i = start; i < array.Length; ++i)
if (crSum + array[i] < maxSum)
{
stack.Add(i);
GeneratePossibilites(array, maxSum, crSum + array[i], stack);
stack.RemoveAt(stack.Count - 1);
}
}
}
我不知道，如果你需要在一个特定的格式或不输出，但你也许可以用这种或其他答案的工作。
我觉得你可以通过建立一个树解决。 在每个节点上你有值的列表。假设这个列表的总和小于所需金额 - 我们称之为的S - ，你可以最多三个孩子这个节点建设：加1到该节点的列表中的一个，通过加3加2，一个一个。建一个孩子的条件将是新列表的总和仍然会小于S. 最后，也就是当你无法生成新的节点，你有你的树的节点所有的序列。
编辑：在C＃我可怜的解释将给予某物这样的：
第一
public class Node
{
public Node()
{
Children = new List<Node>();
}
public static int SumMax { get; set; }
public List<int> Values { get; set; }
public List<Node> Children { get; set; }
public void AddChild(int data)
{
if (Values.Sum() + data < SumMax)
{
Node child = new Node();
child.Values = new List<int>(Values);
child.Values.Add(data);
Children.Add(child);
for (int = data; i < 4; i++)
{
child.AddChild(i);
}
}
}
public void FillSequences(List<List<int>> sequences)
{
if (Values.Count != 0)
{
sequences.Add(Values);
}
foreach (Node child in Children)
{
child.FillSequences(sequences);
}
}
}
，则主：
void Main()
{
Node.SumMax = 10;
Node root = new Node();
root.Values = new List<int>();
for (int i = 1; i < 4; i++)
root.AddChild(i);
List<List<int>> sequences = new List<List<int>>();
root.FillSequences(sequences);
//here you've got your sequences results in "sequences" and you can do what you want
}
我不知道这是否是标准的不够好，但它大致的工作。我希望它适合你的需要......
修改：避免同一序列的产生，就可以“命令”的树：一个节点不能产生一个孩子比其一个较低的值。因此，在该的AddChild方法中，我们开始循环在“数据”，而不是在1
