3

私は次の情報を与えられたすべての組み合わせを見つける方法を理解しようとしています：

JSONデータセットから始めます。

var choices = { 1: {'Q': 100, 'R': 150, 'W' : 250, 'T', 30},
                2: {'Q': 90, 'R': 130, 'W' : 225, 'T', 28},
                3: {'Q': 80, 'R': 110, 'W' : 210, 'T', 25},
                4: {'Q': 70, 'R': 90, 'W' : 180, 'T', 22},
                5: {'Q': 60, 'R': 70, 'W' : 150, 'T', 18},
                6: {'Q': 50, 'R': 50, 'W' : 110, 'T', 15},
                7: {'Q': 40, 'R': 30, 'W' : 80, 'T', 11},
                8: {'Q': 30, 'R': 25, 'W' : 50, 'T', 8},
                9: {'Q': 20, 'R': 10, 'W' : 25, 'T', 5},
                10: {'Q': 10, 'R': 5, 'W' : 15, 'T', 3}
              };

私が理解しようとしているのは、このデータセットを取得し、各行の「Q」、「R」、「W」、または「T」要素のいずれかを選択するときに可能なすべての組み合わせを生成する方法です。

だから私の最終結果がこのようなものになることを願っています

var allChoices = { 0: {1: {'Q': 100},
                       2: {'R': 130},
                       3: {'W' : 210},
                       4: {'W' : 180},
                       5: {'T', 18},
                       6: {'R': 50,},
                       7: {'Q': 40,},
                       8: {'T', 8},
                       9: {'R': 10},
                      10: {'W' : 15},
                     },
                 1: {...},
                 ...
                 1048576: {...}

              };

視覚化するのが最も簡単だと思うのでJSONを使用しましたが、C＃でこれを実現する方法を知っている人はいますか？

これが十分に明確でない場合は、この質問を正確に行う方法を理解するのに苦労していることを知らせてください。

4

4 に答える 4

3

10桁の基数4の数値です。

class Program
{
    static void Main(string[] args)
    {
        int baseN = 4;
        int maxDigits = 10;
        var max = Math.Pow(baseN, maxDigits);
        for (int i = 0; i < max; i++)
        { // each iteration of this loop is another unique permutation
            var digits = new int[maxDigits];
            int value = i;
            int place = digits.Length - 1;
            while (value > 0)
            {
                int thisdigit = value % baseN;
                value /= baseN;
                digits[place--] = thisdigit;
            }

            int choice = 0;
            foreach (var digit in digits)
            {
                choice ++;
                //Console.Write(digit);
                switch (digit)
                {
                    case 0: break; //choose Q from choice
                    case 1: break; //choose R from choice
                    case 2: break; //choose W from choice
                    case 3: break; //choose T from choice
                }
            }
            //Console.WriteLine();
            // add it to your list of all permutations here
        }
        Console.WriteLine("Done")
        Console.ReadLine();
    }
}
于 2012-02-16T16:29:38.617 に答える
3

あなたが探しているのは、10配列のデカルト積です（より適切に呼ばれていると思うので、10進デカルト積）。Eric Lippertは、任意の数のアレイに対してこれを行うための優れた（そして非常に高度な）記事をここに書いています：http：//ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

その結果、次の関数があなたの望むことを実行すると思います。

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
  IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
  return sequences.Aggregate(
    emptyProduct,
    (accumulator, sequence) =>
      from accseq in accumulator
      from item in sequence
      select accseq.Concat(new[] {item}));
}

あなたの場合の入力はあなたの10個の配列の配列です。出力は、各ステップで10項目の無数を返す無数になります。基本的に、その関数の出力を繰り返し処理して、考えられるすべての順列を取得します。

于 2012-02-16T16:51:55.573 に答える
2

深さ優先再帰を使用してこれを行う方法は次のとおりです。私のマシンで実行するには約3秒かかります。また、これは、4列ではなく5列の場合、PAIRCOUNTを5に変更し、必要に応じて追加のペアを追加することで、任意のサイズのペアに対して機能します。

    void Main()
    {
        var OriginValues = new List<KeyValuePair<char, int>>();
        OriginValues.Add(new KeyValuePair<char, int>('Q', 100));
        OriginValues.Add(new KeyValuePair<char, int>('R', 150));
        OriginValues.Add(new KeyValuePair<char, int>('W', 250));
        OriginValues.Add(new KeyValuePair<char, int>('T', 30));

        OriginValues.Add(new KeyValuePair<char, int>('Q', 90));
        OriginValues.Add(new KeyValuePair<char, int>('R', 130));
        OriginValues.Add(new KeyValuePair<char, int>('W', 225));
        OriginValues.Add(new KeyValuePair<char, int>('T', 28));

        OriginValues.Add(new KeyValuePair<char, int>('Q', 80));
        OriginValues.Add(new KeyValuePair<char, int>('R', 110));
        OriginValues.Add(new KeyValuePair<char, int>('W', 210));
        OriginValues.Add(new KeyValuePair<char, int>('T', 25));

        ///... and the other 7

        var AllPermutation = new List<List<KeyValuePair<char, int>>>();
        Recurse(OriginValues, ref AllPermutation);

        //all results will be in AllPermutation now

    }

    const int PAIRCOUNT = 4;
    void Recurse(List<KeyValuePair<char, int>> OriginValues, ref List<List<KeyValuePair<char, int>>> result, List<KeyValuePair<char, int>> itemset = null)
    {
        itemset = itemset ?? new List<KeyValuePair<char, int>>();
        var temp = new List<KeyValuePair<char, int>>(itemset);
        if (itemset.Count == OriginValues.Count / PAIRCOUNT)
        {
            result.Add(temp);
            return;
        }
        for (int x = 0; x < PAIRCOUNT; x++)
        {
            temp.Add(OriginValues[itemset.Count * PAIRCOUNT + x]);
            Recurse(OriginValues, ref result,  temp);
            temp = new List<KeyValuePair<char, int>>(itemset);
        }

    }
于 2012-02-16T17:00:03.330 に答える
1

これをチェックしてください：LinqのCombination Generator

LINQを使用しない別のソリューションでは、行ごとに4つだけでこれを実行すると仮定すると、最も簡単な方法は、ブルートフォース攻撃を行い、ネストされたforeachループを実行することです。

foreach ( choice in allChoices )
{
    foreach ( choice in allChoices )
    {
        foreach ( choice in allChoices )
        {
            foreach ( choice in allChoices )
            {
                // combine and add to a collection
            }
        }
    }
}

編集：foreachループでループするオブジェクトを追加しました

于 2012-02-16T16:14:57.863 に答える