C# advanced permutation scenario

Question

I am trying to figure how how to find all the combinations given the following information:

I start with a JSON dataset:

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

What I'm trying to figure out is how I can take this dataset, and generate all possible combinations when selecting either the 'Q', 'R', 'W', or 'T' element for each row.

So I hope my end result will be something like this

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: {...}

              };

I used JSON because I think it is the easiest to visualize but does anyone know how I could go about accomplishing this in c#?

Let me know if this not clear enough I'm having a hard time figuring out how exactly to ask this question.

Answer 1

What you are looking for is the Cartesian Product of 10 arrays (10-ary Cartesian product as I think it is more properly called). Eric Lippert wrote a good (and quite advanced) article on doing this for an arbtirary number of arrays here: http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

The upshot of it is that I think the following function will do what you want:

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

The input in your case is an array of your 10 arrays. The output would be an ienumerable that would return at each step an ienumerable of ten items. You would basically iterate over the output of that function to get all your possible permutations.

Answer 2

Here's How to do it using depth first Recursion. Takes about 3 seconds to run on my machine. Also this will work for an arbitrary sized pairing by changing the PAIRCOUNT to say 5 if you had 5 columns instead of 4 and just .add the additional Pairs as appropriate.

    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 3

It's a 10 digit base 4 number.

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 4

check this out: Combination Generator in Linq

Another solution without LINQ, assuming you will be doing this on only 4 things per row, the easiest thing is to just brute force it and do nested foreach loops.

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

edit: added objects to loop over in foreach loops