Building a Matrix of Combinations

Question

I'm sure this has been asked a million times, but when I searched all the examples didn't quite fit, so I thought I should ask it anyway.

I have two arrays which will always contain 6 items each. For example:

string[] Colors=
    new string[] { "red", "orange", "yellow", "green", "blue", "purple" };

string[] Foods=
    new string[] { "fruit", "grain", "dairy", "meat", "sweet", "vegetable" };

Between these two arrays, there are 36 possible combinations(e.g. "red fruit", "red grain").

Now I need to further group these into sets of six unique values.

For example:

meal[0]=
    new Pair[] { 
        new Pair { One="red", Two="fruit" }, 
        new Pair { One="orange", Two="grain" }, 
        new Pair { One="yellow", Two="dairy" }, 
        new Pair { One="green", Two="meat" }, 
        new Pair { One="blue", Two="sweet" }, 
        new Pair { One="purple", Two="vegetable" } 
    };

where meal is

Pair[][] meal;

No element can be repeated in my list of "meals". So there is only ever a single "Red" item, and a single "meat" item, etc.

I can easily create the pairs based on the first two arrays, but I am drawing a blank on how best to then group them into unique combinations.

Answer 1

OK, you want a sequence containing all 720 possible sequences. This is a bit trickier but it can be done.

The basic idea is the same as in my previous answer. In that answer we:

• generated a permutation at random
• zipped the permuted second array with the unpermuted first array
• produced an array from the query

Now we'll do the same thing except instead of producing a permutation at random, we'll produce all the permutations.

Start by getting this library:

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

OK, we need to make all the permutations of six items:

Permutations<string> permutations = new Permutations<string>(foods);

What do we want to do with each permutation? We already know that. We want to first zip it with the colors array, turning it into a sequence of pairs, which we then turn into an array. Instead, let's turn it into a List<Pair> because, well, trust me, it will be easier.

IEnumerable<List<Pair>> query = 
    from permutation in permutations
    select colors.Zip(permutation, (color, food)=>new Pair(color, food)).ToList();

And now we can turn that query into a list of results;

List<List<Pair>> results = query.ToList();

And we're done. We have a list with 720 items in it. Each item is a list with 6 pairs in it.

The heavy lifting is done by the library code, obviously; the query laid on top of it is straightforward.

('ve been meaning to write a blog article for some time on ways to generate permutations in LINQ; I might use this as an example!)

Answer 2

There are 720 possible combinations that meet your needs. It is not clear from your question whether you want to enumerate all 720 or choose one at random or what. I'm going to assume the latter.

UPDATE: Based on comments, this assumption was incorrect. I'll start a new answer.

---

First, produce a permutation of the second array. You can do it in-place with the Fischer-Yates-Knuth shuffle; there are many examples of how to do so on StackOverflow. Alternatively, you could produce a permutation with LINQ by sorting with a random key.

The former technique is fast even if the number of items is large, but mutates an existing array. The second technique is slower, particularly if the number of items is extremely large, which it isn't.

The most common mistake people make with the second technique is sorting on a guid. Guids are guaranteed to be unique, not guaranteed to be random.

Anyway, produce a query which, when executed, permutes the second array:

Random random = new Random();
IEnumerable<string> shuffled = from food in foods 
                               orderby random.NextDouble() 
                               select food;

A few other caveats:

• Remember, the result of a query expression is a query, not a set of results. The permutation doesn't happen until you actually turn the thing into an array at the other end.
• if you make two instances of Random within the same millisecond, you get the same sequence out of them both.
• Random is pseudo-random, not truly random.
• Random is not threadsafe.

Now you can zip-join your permuted sequence to the first array:

IEnumerable<Pair> results = colors.Zip(shuffled, (color, food)=>new Pair(color, food));

Again, this is still a query representing the action of zipping the two sequences together. Nothing has happened yet except building some queries.

Finally, turn it into an array. This actually executes the queries.

Pair[] finalResults = results.ToArray();

Easy peasy.

Answer 3

Upon request, I will be specific about how I view the problem in regards to sorting. I know that since C# is a higher level language there are tons of quick and easy libraries and objects that can be used to reduce this to minimal code. This answer is actually attempting the solve the question by implementing sorting logic.

When initially reading this question I was reminded of sorting a deck of cards. The two arrays are very similar to an array for suit and an array for face value. Since one way to solve a shuffle is to randomize the arrays and then pick a card combined of both, you could apply the same logic here.

Sorting as a possible solution

The Fisher-Yates sorting algorithm essentially loops through all the indices of the array swapping the current index with a random index. This creates a fairly efficient sorting method. So then how does this apply to the problem at hand? One possible implementation could be...

    static Random rdm = new Random();
    public string[] Shuffle(string[] c)
    {
        var random = rdm;
        for (int i = c.Length; i > 1; i--)
        {
            int iRdm = rdm.Next(i);
            string cTemp = c[iRdm];
            c[iRdm] = c[i - 1];
            c[i - 1] = cTemp;
        }
        return c;
    }

Source: Fisher-Yates Shuffle

The code above randomizes the positions of values within the string array. If you passed the Colors and Food arrays into this function, you would get unique pairings for your Pairs by referencing a specific index of both.

Since the array is shuffled, the pairing of the two arrays at index 0,1,2,etc are unique. The problem however asks for Pairs to be created. A Pair class should then be created that takes in a value at a specific index for both Colors and Foods. ie...Colors[3] and Foods[3]

 public class Pair
{
     public string One;
     public string Two;
     public Pair(string m1, string m2)
     {
         One = m1;
         Two = m2;
     }
}

Since we have sorted arrays and a class to contain the unique parings, we simply create the meal array and populate it with Pairs.

If we wanted to create a new pair we would have...

Pair temp = new Pair(Colors[0],Foods[0]);

With this information we can finally populate the meal array.

    Pair[] meal = new Pair[Colors.Length - 1];
    for (int i = 0; i < Colors.Length - 1; i++)
    {
        meal[i] = new Pair(Colors[i],Foods[i]);
    } 

This section of code creates the meal array and defines its number of indices by the length of Colors. The code then loops through the total number of Color values while creating new pair combos and dropping them in meal. This method assumes the length of the arrays are identical, a check could easily be made for the smallest array.

Full Code

private void Form1_Load(object sender, EventArgs e)
        {
            string[] Colors = new string[] { "red", "orange", "yellow", "green", "blue", "purple" };
            string[] Foods = new string[] { "fruit", "grain", "dairy", "meat", "sweet", "vegetable" };
            Colors = Shuffle(Colors);
            Foods = Shuffle(Foods);
            Pair[] meal = new Pair[Colors.Length - 1];
            for (int i = 0; i < Colors.Length - 1; i++)
            {
                meal[i] = new Pair(Colors[i],Foods[i]);
            }
        }
        static Random rdm = new Random();
        public string[] Shuffle(string[] c)
        {
            var random = rdm;
            for (int i = c.Length; i > 1; i--)
            {
                int iRdm = rdm.Next(i);
                string cTemp = c[iRdm];
                c[iRdm] = c[i - 1];
                c[i - 1] = cTemp;
            }
            return c;
        }
    }
    public class Pair
    {
         public string One;
         public string Two;
         public Pair(string m1, string m2)
         {
             One = m1;
             Two = m2;
         }
     }

-Original Post-

You can simply shuffle the array. This will allow for the same method to populate meal, but with different results. There is a post on Fisher-Yates shuffle Here