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

木を作ることで解決できると思います。各ノードには、値のリストがあります。このリストの合計が必要な合計よりも少ないと仮定すると（Sと呼びましょう）、このノードの子を最大3つ作成できます。1つはこのノードのリストに1を追加し、もう1つは2を追加し、もう1つは3を追加します。子を作成するための条件は、新しいリストの合計がSよりも少ないことです。最後に、つまり、新しいノードを生成できない場合、ツリーのノードにすべてのシーケンスがあります。

編集：C＃では私の貧弱な説明はそのようなsthを与えるでしょう：

最初：

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ではなく「data」から開始します。

于 2010-04-07T17:16:35.423 に答える
0

これが「標準」であるかどうかはわかりませんが、一番下から始めて作業を進めるのは珍しいことではありません。

1を作る方法は1つあります。

2を作成するには2つの方法があります。1で始まる方法と2で始まる方法、3で始まる方法の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 に答える
0

少しひねりを加えて、パーティションに興味があるようです。この関数はトリックを行います。基本的に、合計が目標の合計よりも少ない間、スタックに数値を追加し続け、各ステップでスタックを印刷します。

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 に答える