C # расширенный сценарий перестановки

Question

Я пытаюсь понять, как найти все комбинации, используя следующую информацию:

Я начинаю с набора данных 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 #?

Дайте мне знать, еслиэто не достаточно ясно, мне трудно понять, как именно задать этот вопрос.

Answer 1

Это 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();
    }
}

Answer 2

То, что вы ищете, это декартово произведение из 10 массивов (10-арное декартово произведение, как мне кажется, правильнее называть его). Эрик Липперт написал хорошую (и довольно продвинутую) статью о том, как сделать это для произвольного числа массивов: 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 массивов. Выводом будет перечисляемое значение, которое будет возвращать на каждом шаге перечисляемое количество из десяти элементов. По сути, вы должны перебрать выходные данные этой функции, чтобы получить все возможные варианты.

Answer 3

Вот как это сделать, используя глубину первой рекурсии.Требуется приблизительно 3 секунды, чтобы бежать на моей машине.Также это сработает для пары произвольного размера, изменив PAIRCOUNT на 5, если у вас было 5 столбцов вместо 4, и просто добавьте дополнительные пары в зависимости от ситуации.

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

    }

Answer 4

проверить это: Комбинированный генератор в Linq

Другое решение без 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
            }
        }
    }
}

edit: добавлены объекты для зацикливания в циклах foreach