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.

Woa! You didn't split the infinitive! Nice to see that for once. — Almo, Feb 16 '12 at 16:11
Let me understand this. You have a set of characters Q, R, W, T and a set of numbers {100, 130, 210,...}. You now want to relate characters to numbers in every possible combination, correct? — Ani, Feb 16 '12 at 16:15
@ananthonline Exactly. So at the end I could say something like get me the total of every line where the first slot has "Q" basically is what I'm trying to do. I'm trying to find all the possible value totals for 10 selections where each selection has four possibilities. Does that make sense. So it that first example the first result row I would want to know is the total is 761 and the first position was Q. — Collin Estes, Feb 16 '12 at 16:20

weston · Answer 1 · 2012-02-16T16:43:35.010

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

edited Feb 16 '12 at 16:43

answered Feb 16 '12 at 16:29

weston

54,145
21
145
203

I copied this directly and when I run it it seems to go on forever, is that what I should have expected. – Collin Estes Feb 16 '12 at 16:36
No, not at all, it might take a while to print out 1,048,576 lines to the console, but it will stop. Try running it with `6` in the `maxDigits`. – weston Feb 16 '12 at 16:37
Takes no time at all if you remove the `Console.Write` calls, even with `10` in the `maxDigits`. – weston Feb 16 '12 at 16:40
Added `choice` variable to highlight which element of your `choises` array you would use. – weston Feb 16 '12 at 16:44
Ok I think I'm starting to wrap my head around this, so if I want to produce that 1,048,576 combinations exactly I would set that to the max then set the baseN = 10, and the maxDigits = 7. Am I following this right? – Collin Estes Feb 16 '12 at 16:45
No, it's already configured correctly. The length of your choices dataset was 10, these are like the digits in the number, and each has a choice of 4 (Q,R,W,T) making it base 4. And 4^10 = 1,048,576 – weston Feb 16 '12 at 16:49

score 3 · Answer 2 · edited Sep 03 '13 at 20:01

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.

deepee1 · Accepted Answer · 2012-02-16T17:07:11.300

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

    }

score 1 · Answer 4 · edited May 23 '17 at 12:27

1

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

edited May 23 '17 at 12:27

Community

1
1

answered Feb 16 '12 at 16:14

Scott M.

7,313
30
39

I thought this, but doesn't he need 10 `foreach`s? Each one going through the 4 choices? – weston Feb 16 '12 at 16:19
@weston Yeah that is what is confusing me about doing it this way, I'm not sure really how to set it up right – Collin Estes Feb 16 '12 at 16:20
I'm not sure you need 10. If you have 4 propeties you want to hit, you can `foreach` over the whole collection and access each property in turn. 4 properties means 4 foreach loops. I still think the LINQ permutation solution I linked to is the cleanest solution because it's functional and recursive and declares what you want vs. manually looping. – Scott M. Feb 16 '12 at 16:23
Scott: each output should have 10 items so I'd say you need 10. You'd have to provide code of what you are doing in the middle there to convince me otherwise... – Chris Feb 16 '12 at 16:53

C# advanced permutation scenario

4 Answers4

Linked