4

给定以下唯一数字（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，但无法弄清楚。另外，我正在尝试一种基于堆栈的方法，但我仍然没有成功。

任何想法？

4

5 回答 5

2

我认为这是最容易递归编写的，纯 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

请注意，这不是最有效的解决方案。

于 2010-04-07T17:18:04.990 回答
0

似乎您对partitions感兴趣，有点曲折。这个函数可以解决问题。基本上，当它们的总和小于目标总和时，继续将数字添加到堆栈中，然后在每一步打印堆栈。

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

我不确定您是否需要特定格式的输出，但您可能可以使用这个或其他答案。

于 2010-04-07T17:33:00.547 回答
0

我认为你可以通过建造一棵树来解决这个问题。在每个节点上，您都有一个值列表。假设这个列表的总和小于所需的总和——我们称之为 S——，你最多可以为这个节点构建三个子节点：一个通过在这个节点的列表中添加 1，一个通过添加 2，一个通过添加 3 . 建立一个孩子的条件是新列表的总和仍然小于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 开始循环。

于 2010-04-07T17:16:35.423 回答
0

我不知道这是否是“标准”，但从底部开始向上工作并不罕见。

有 1 种方法可以生成 1。

2有2种方法，分为3类：以1开头的，以2开头的，以3开头的。最后一类当然是空的。

计算N的方法，考虑从1开始的N-1的方法，从2或1开始的N-2的方法，以及从3、2或1开始的N-3的方法。

于 2010-04-07T17:20:51.247 回答
0

在我看来，“最简单”（如果不是最有效的话）的方法是只取你的数字集，并取它的所有排列，然后过滤掉总和高于截止点的那些。

于 2010-04-07T17:21:08.750 回答