6

以下の C# コードを変更して、可能なすべての順列を繰り返しなしでリストするにはどうすればよいですか? 例: サイコロを 2 回振った結果は 1,1,2 になるため、2,1,1 は表示されません。

以下は私のコードです：

string[] Permutate(int input)
{
        string[] dice;
        int numberOfDice = input;
        const int diceFace = 6;
        dice = new string[(int)Math.Pow(diceFace, numberOfDice)];
        int indexNumber = (int)Math.Pow(diceFace, numberOfDice);
        int range = (int)Math.Pow(diceFace, numberOfDice) / 6;

        int diceNumber = 1;
        int counter = 0;

        for (int i = 1; i <= indexNumber; i++)
        {
            if (range != 0)
            {
                dice[i - 1] += diceNumber + " ";
                counter++;
                if (counter == range)
                {
                    counter = 0;
                    diceNumber++;
                }
                if (i == indexNumber)
                {
                    range /= 6;
                    i = 0;
                }
                if (diceNumber == 7)
                {
                    diceNumber = 1;
                }
            }
            Thread.Sleep(1);
        }
        return dice;
    }
4

5 に答える 5

1

二項係数を扱うための一般的な関数を処理するクラスを作成しました。これは、問題が該当するタイプの問題です。次のタスクを実行します。

  1. 任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。この方法により、この種の問題を簡単に解決できます。

  2. K インデックスを、並べ替えられた二項係数テーブル内のエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的性質を使用して行われます。私の論文はこれについて語っています。この手法を発見して公開したのは私が最初だと思いますが、間違っている可能性があります。

  3. ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。

  4. Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。

  5. このクラスは .NET C# で記述されており、問題に関連するオブジェクト (存在する場合) をジェネリック リストを使用して管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を実行するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。

  6. クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

于 2012-09-26T23:07:15.107 に答える
0

質問の重要な部分は、(順序に関係なく) 個別のセットが必要であるということです。したがって、たとえば、[1, 2, 1] のサイコロの出目は、[1, 1, 2] のサイコロの出目と同じです。

この猫の皮をむく方法はいくつかあると思いますが、最初に頭に浮かぶのは、サイコロのリストを必要な方法で比較する EqualityComparer を作成し、その Distinct()メソッドで LINQ を使用することです。

EqualityComparerこれは 2 を取りList<int>、要素がすべて等しい場合 (順序に関係なく) 等しいことを示します。

    private class ListComparer : EqualityComparer<List<int>>
    {
        public override bool Equals(List<int> x, List<int> y)
        {
            if (x.Count != y.Count)
                return false;
            x.Sort();
            y.Sort();
            for (int i = 0; i < x.Count; i++)
            {
                if (x[i] != y[i])
                    return false;
            }
            return true;
        }
        public override int GetHashCode(List<int> list)
        {
            int hc = 0;
            foreach (var i in list)
                hc ^= i;
            return hc;
        }
    }

そして、これを使用するコードは次のとおりです。私はLINQを使用してすべての組み合わせのリストを作成しています...ネストされたforループでこれを行うこともできますが、何らかの理由でこれが好きです:

    public static void Main()
    {
        var values = new[] { 1,2,3,4,5,6 };
        var allCombos = from x in values
                        from y in values
                        from z in values
                        select new List<int>{ x, y, z };
        var distinctCombos = allCombos.Distinct(new ListComparer());

        Console.WriteLine("#All combos: {0}", allCombos.Count());
        Console.WriteLine("#Distinct combos: {0}", distinctCombos.Count());
        foreach (var combo in distinctCombos)
            Console.WriteLine("{0},{1},{2}", combo[0], combo[1], combo[2]);
    }

それが役立つことを願っています!

于 2012-07-07T13:10:09.453 に答える
0

私も数学が苦手なので、参考になるかも知れませんが…

Program.cs

namespace Permutation
{
    using System;
    using System.Collections.Generic;

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Generating list.");

            var dice = new List<ThreeDice>();

            for (int x = 1; x <= 6; x++)
            {
                for (int y = 1; y <= 6; y++)
                {
                    for (int z = 1; z <= 6; z++)
                    {
                        var die = new ThreeDice(x, y, z);

                        if (dice.Contains(die))
                        {
                            Console.WriteLine(die + " already exists.");
                        }
                        else
                        {
                            dice.Add(die);
                        }
                    }
                }
            }

            Console.WriteLine(dice.Count + " permutations generated.");

            foreach (var die in dice)
            {
                Console.WriteLine(die);
            }

            Console.ReadKey();
        }
    }
}

ThreeDice.cs

namespace Permutation
{
    using System;
    using System.Collections.Generic;

    public class ThreeDice : IEquatable<ThreeDice>
    {
        public ThreeDice(int dice1, int dice2, int dice3)
        {
            this.Dice = new int[3];
            this.Dice[0] = dice1;
            this.Dice[1] = dice2;
            this.Dice[2] = dice3;
        }

        public int[] Dice { get; private set; }

        // IEquatable implements this method. List.Contains() will use this method to see if there's a match.
        public bool Equals(ThreeDice other)
        {
            // Get the current dice values into a list.
            var currentDice = new List<int>(this.Dice);

            // Check to see if the same values exist by removing them one by one.
            foreach (int die in other.Dice)
            {
                currentDice.Remove(die);
            }

            // If the list is empty, we have a match.
            return currentDice.Count == 0;
        }

        public override string ToString()
        {
            return "<" + this.Dice[0] + "," + this.Dice[1] + "," + this.Dice[2] + ">";
        }
    }
}

幸運を。

于 2012-07-07T08:22:15.673 に答える
0

これは、再帰を使用する一般的なC＃バージョンです（基本的に、再帰メソッドはサイコロの数またはサイコロが投げられた回数を受け取ります）、すべての組み合わせ文字列を返します（例、質問によると「3」の場合-56のようなものがあります組み合わせ）。

public string[] GetDiceCombinations(int noOfDicesOrnoOfTossesOfDice)
        {
            noOfDicesOrnoOfTossesOfDice.Throw("noOfDicesOrnoOfTossesOfDice",
                n => n <= 0);
            List<string> values = new List<string>();
            this.GetDiceCombinations_Recursive(noOfDicesOrnoOfTossesOfDice, 1, "",
                values);
            return values.ToArray();
        }
        private void GetDiceCombinations_Recursive(int size, int index, string currentValue,
            List<string> values)
        {
            if (currentValue.Length == size)
            {
                values.Add(currentValue);
                return;
            }
            for (int i = index; i <= 6; i++)
            {
                this.GetDiceCombinations_Recursive(size, i, currentValue + i, values);
            }
        }

以下は対応するテストです...

[TestMethod]
        public void Dice_Tests()
        {
            int[] cOut = new int[] { 6, 21, 56, 126 };
            for(int i = 1; i<=4; i++)
            {
                var c = this.GetDiceCombinations(i);
                Assert.AreEqual(cOut[i - 1], c.Length);
            }
        }
于 2014-08-08T16:01:36.640 に答える