Part I. Introduction
Our quest starts with the following puzzle:
"How many numbers can you make using three arithmetic operations consisting of addition, subtraction, multiplication, and division using the whole numbers from 1 to 5 inclusive and what are they?"
It is often easier to break a hard problem down and try to solve a simpler version before attempting to solve the whole thing. In this case, let's take a look at the number or ways we can combine two operators consisting of just add and subtract.
[+, +]
[+, -]
[-, +]
[-, -]
Our resulting group of groups ends up being the Cartesian product of the group [+, -] with itself.
Similarly, if we look at all the way we can subtract the numbers 1 and 2 we also have a Cartesian product problem:
1-1
1-2
2-1
2-2
or
We'll approach our problem by writing code to find the Cartesian product of the required groups: the group of operators and the group of numbers. We need to find all possible ways to combine the group of operators [+, -, *, /] three times and all possible ways to combine the group of numbers [1, 2, 3, 4, 5] four times. In fact, this seems like functionality that would potentially be useful in solving other problems so we'll approach the solution by developing code that will be generic and reusable.
Part II. IEnumerable<> -- Combining Objects to Make Groups
We'll be at using the common interface
IEnumerable<T> as defining a group because it is an interface that is present in all generic groups and is interface that enables us to use the "
foreach(item in group){ do something with item }" language construct to iterate over the items group. If we can write a library of methods that use the
IEnumerable<T> interface our solution will have maximum reusability.
Where things may start getting a little confusing is that the result of our Cartesian product function will be a group of groups called a matrix or from the perspective of C#:
IEnumerable<IEnumerable<T>>.
Fortunately, there is a C# language keyword that allows us to easily create iterators:
yield. Again, let's break down the problem into the simplest possible 'chunks'. Let's look at a generic method that returns an iterator containing two objects that are used as input:
public static class Combiner
{
public static IEnumerable<T> Group<T>(T a, T b)
{
yield return a;
yield return b;
}
} |
Our utility method allows us to group two items and iterate over them as in the following example.
IEnumerable<Char> collection = Combiner.Group('x', 'y');
foreach (Char c in collection)
Console.WriteLine(c); |
There are a couple more basic things we'll need in our bag of tricks in terms of combining objects. What if we need to append another item to our already existing
IEnumerable<T> collection? We could use the following two methods to add items at the beginning or the end of our collection.
// add the new item at the beginning of the collection
public static IEnumerable<T> Append<T>(T a, IEnumerable<T> b)
{
yield return a;
foreach (T item in b) yield return item;
}
// add the new item at the end of the collection
public static IEnumerable<T> Append<T>(IEnumerable<T> a, T b)
{
foreach (T item in a) yield return item;
yield return b;
} |
This can be utilized in the following code:
IEnumerable<Char> collection = Combiner.Group('x', 'y');
collection = Combiner.Append(collection, 'z'); // add 'z' at the end
foreach (Char c in collection)
Console.WriteLine(c); |
This will produce the following results:
x
y
z
Similarly, we can now also add items to the beginning of our collection:
IEnumerable<Char> collection = Combiner. Group('x', 'y');
collection = Combiner.Append(collection, 'z'); // add 'z' at the end
collection = Combiner.Append('w', collection); // add 'w' to the front
foreach (Char c in collection)
Console.WriteLine(c); |
Which produces the following results
w
x
y
z
We may also need to combine two separate collections which can be accomplished with the following code:
public static IEnumerable<T> Combine<T>(IEnumerable<T> a, IEnumerable<T> b)
{
foreach (T item in a) yield return item;
foreach (T item in b) yield return item;
} |
So now that we have a basic set of generic reusable methods for working with groups, we need to start looking at an enumerable matrix (
a groups-of-groups). Let's say we have two groups of characters ['a', 'b'] and ['c'
, 'd'] which we derive using our existing Combine() method.
IEnumerable<Char>
group1 = Combiner.Combine('a', 'b'),
group2 = Combiner.Combine('c', 'd'); |
Now we need a way to represent, these two groups as a enumerable matrix and can do so by reusing our
Combine() method:
IEnumerable<IEnumerable<Char>>
matrix = Combiner.Group(group1, group2); |
At first, this may seem a little confusing, but whenever you see
IEnumerable<IEnumerable<T>>, you can think of it as a enumerable matrix (or a multi-dimensional array) which could in all reality be a more generic representation of an actual multi-dimensional array like
T[][]. As a matter of fact, it is completely valid to think of multi-dimensional arrays in terms of how they are enumerated as in the following code which will basically produce the results we achieved by grouping two groups.
IEnumerable<IEnumerable<Char>>
matrix2 = new Char[][]
{
new Char[]{ 'a', 'b' },
new Char[]{ 'c', 'd' }
}; |
Using our Combiner() method is much more flexible than using the array approach because we can add items to the beginning and end of our collections which is not so easy using
C#'s immutable arrays but there is no reason we could not combine the two as you will see later in this article.
As a side note, let's look at two utility methods to display our collections to the console.
This first method displays a generic list of things by calling each list item's
ToString() method:
private static void DisplayResult<T>(IEnumerable<T> subList)
{
foreach (T c in subList)
Console.Write(c.ToString());
Console.WriteLine();
} |
This second method will display our group of groups by calling the previous method on all sub-groups:
private static void DisplayResult<T>(IEnumerable<IEnumerable<T>> result)
{
foreach (IEnumerable<T> subList in result)
DisplayResult(subList);
Console.WriteLine();
} |
This way we can view our groups and the following code…
IEnumerable<IEnumerable<Char>>
matrix2 = new Char[][]
{
new Char[]{ 'a', 'b' },
new Char[]{ 'c', 'd' }
};
DisplayResult(matrix2); |
Will produce the result:
abcd
Combining Objects with Groups
The next thing we'll want to be able to do is combine an object with an enumerable matrix of the same type, appending the new object either at the beginning or end of each subgroup. For example, let's say we have our enumerable matrix as in the following code and wish to append a 'z' at the end of each group.
IEnumerable<IEnumerable<Char>>
matrix2 = new Char[][]
{
new Char[]{ 'a', 'b' },
new Char[]{ 'c', 'd' }
}; |
In order to do this, we'll need a method that we pass the enumerable matrix to and will append 'z' at the end of each subgroup and return the resulting enumerable matrix as follows:
public static IEnumerable<IEnumerable<T>> Combine<T>(IEnumerable<IEnumerable<T>> a, T b)
{
foreach (IEnumerable<T> aGroup in a)
yield return Append(aGroup, b);
} |
This method will work great
as long as there are items in the 'a' parameter. So how do we handle the case where there are no items in 'a'? First, we'll have to keep a flag to determine if 'a' has been iterated over and then determine what to return if a is empty. If a is empty, we'll need to return the 'b' parameter in terms of
a enumerable matrix. In other words, we'll have to convert the 'b' parameter to a 'parent' group with one member which is a group with one item. This way 'b' is now placed in an enumerable matrix.
public static IEnumerable<IEnumerable<T>> Combine<T>(IEnumerable<IEnumerable<T>> a, T b)
{
Boolean found = false;
foreach (IEnumerable<T> aGroup in a)
{
found = true;
yield return Append(aGroup, b);
}
if (!found)
yield return new T[] { b };
} |
Likewise, we'll want a method that will append a new object at the beginning of every subgroup in an enumerable matrix:
public static IEnumerable<IEnumerable<T>> Combine<T>(T a, IEnumerable<IEnumerable<T>> b)
{
Boolean found = false;
foreach (IEnumerable<T> bGroup in b)
{
found = true;
yield return Append(a, bGroup);
}
if (!found)
yield return new T[] { a };
} |
In order to append a new group to the beginning or end of each subgroup in an enumerable matrix we can follow the pattern above:
public static IEnumerable<IEnumerable<T>> Combine<T>(IEnumerable<T> a, IEnumerable<IEnumerable<T>> b)
{
Boolean found = false;
foreach (IEnumerable<T> bGroup in b)
{
found = true;
yield return Append(a, bGroup);
}
if (!found)
yield return a;
}
public static IEnumerable<IEnumerable<T>> Combine<T>(IEnumerable<IEnumerable<T>> a, IEnumerable<T> b)
{
Boolean found = false;
foreach (IEnumerable<T> aGroup in a)
{
found = true;
yield return Append(aGroup, b);
}
if (!found)
yield return b;
} |
And finally, we will need to combine two enumerable matrices, appending each subgroup in one matrix to each subgroup in the other matrix.
public static IEnumerable<IEnumerable<T>> Combine<T>(IEnumerable<IEnumerable<T>> a, IEnumerable<IEnumerable<T>> b)
{
Boolean found = false;
foreach (IEnumerable<T> groupa in a)
{
found = true;
foreach (IEnumerable<T> groupB in b)
yield return Append(groupa, groupB);
}
if (!found)
foreach (IEnumerable<T> groupB in b)
yield return groupB;
} |
If this is your first time thinking about collections in this way it can take a couple of reads before it all makes sense, but hopefully you are still with me because now we get to see how to use our very flexible library of methods to easily solve some difficult problems. If you have any questions, please add them at the end of this article and I'll do my best to answer them.
Part III. Finally… The Cartesian Product
Now that we have the necessary tools, let's look at the code for producing the Cartesian product of any two groups.
Before we get started, let's again think about the simplest case. What is the Cartesian product of one group with an empty group? Let's say we have a group consisting of ['a', 'b', 'c'] and want to append this group to the end of every item of an empty group. What we would end up with is a matrix containing three subgroups each with one item: [['a'], ['b'], ['c']]. We can accomplish this with the following code:
public static class CProd
{
private static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> input)
{
foreach (T item in input)
yield return new T[] { item };
}
} |
So now we can easily get our Cartesian product by combining two groups as follows:
IEnumerable<IEnumerable<Char>>
group1 = CProd.Combinations(Combiner.Group('a', 'b')),
group2 = CProd.Combinations(Combiner.Group('c', 'd'));
IEnumerable<IEnumerable<Char>>
cartesianProduct = Combiner.Combine<Char>(group1, group2);
DisplayResult(cartesianProduct); |
This produces the result we are expecting:
ac
ad
bc
bd
There may be cases where we want the Cartesian products of more than just two groups. In order to get the Cartesian products of an arbitrarily long list of groups, we can utilize our previously discussed method to provide functionally for finding the Cartesian product of
any number of groups.
public static class CProd
{
public static IEnumerable<IEnumerable<T>> Combinations<T>(params IEnumerable<T>[] input)
{
IEnumerable<IEnumerable<T>> result = new T[0][];
foreach (IEnumerable<T> item in input)
result = Combiner.Combine(result, Combinations(item));
return result;
}
private static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> input)
{
foreach (T item in input)
yield return new T[] { item };
}
} |
And now we can execute the following simplified code and get the same result:
IEnumerable<Char>
group1 = Combiner.Group('a', 'b'),
group2 = Combiner.Group('c', 'd');
IEnumerable<IEnumerable<Char>>
cartesianProduct = CProd.Combinations(group1, group2);
DisplayResult(cartesianProduct); |
One Group: How Many Ways?
Getting back to the problem at the beginning of the article
"How many numbers can you make using three arithmetic operations consisting of addition, subtraction, multiplication, and division using the whole numbers from 1 to 5 inclusive and what are they?"
In order to find all the set containing all possible ways to combine the set ['+', '-', '*', '/'] three times, we'll need the Cartesian product of the group by itself three times. We just need to expose the Cartesian product method in this way using one utility method:
public static class Chooser
{
public static IEnumerable<IEnumerable<T>> Choose<T>(IEnumerable<T> item, Int32 count)
{
IEnumerable<IEnumerable<T>> result = new T[0][];
for (Int32 i = 0; i < count; i++)
result = Combiner.Combine(result, CProd.Combinations(item));
return result;
}
} |
This will allow us to get the Cartesian product of the set by itself three times:
IEnumerable<IEnumerable<Char>>
cartesianProduct = Chooser.Choose(new Char[] { '+', '-', '*', '/' }, 3);
DisplayResult(cartesianProduct); |
Which gives us the following result set:
[+++], [++-], [++*], [++/], [+-+], [+--], [+-*], [+-/], [+*+], [+*-], [+**], [+*/], [+/+], [+/-], [+/*], [+//], [-++], [-+-], [-+*], [-+/], [--+], [---], [--*],[--/], [-*+], [-*-], [-**], [-*/], [-/+], [-/-], [-/*], [-//], [*++], [*+-], [*+*], [*+/], [*-+], [*--], [*-*], [*-/], [**+], [**-], [***], [**/], [*/+], [*/-], [*/*], [*//], [/++], [/+-], [/+*], [/+/], [/-+], [/--], [/-*], [/-/], [/*+], [/*-], [/**], [/*/], [//+], [//-], [//*], [///]
The Solution
To easily solve our initial problem, we can use our new method library:
IEnumerable<IEnumerable<Char>>
operatorGroups = Chooser.Choose(new Char[] { '+', '-', '*', '/' }, 3);
IEnumerable<IEnumerable<Double>>
valueGroups = Chooser.Choose(new Double[] { 1.0, 2.0, 3.0, 4.0, 5.0 }, 4);
List<Double> result = new List<Double>();
foreach(IEnumerable<Double> valueGroup in valueGroups)
foreach (IEnumerable<Char> operatorGroup in operatorGroups)
{
List<Double> vals = new List<double>(valueGroup);
List<Char> ops = new List<char>(operatorGroup);
Boolean valid = true;
Double value = vals[0];
for (int i = 0; i < ops.Count; i++)
{
switch (ops[i])
{
case '+':
value += vals[i + 1];
break;
case '-':
value -= vals[i + 1];
break;
case '*':
value *= vals[i + 1];
break;
case '/':
if (vals[i + 1] == 0) // won't happen, but makes me nervous anyways
valid = false;
else
value /= vals[i + 1];
break;
default:
throw new ArgumentException("Undefined operator");
}
if (!valid)
break;
}
// round to avoid dupes that are not really dupes
value = Math.Round(value, 4, MidpointRounding.AwayFromZero);
if (valid && !result.Contains(value))
result.Add(value);
}
Console.WriteLine(result.Count);
Boolean first = true;
result.Sort();
result.ForEach(delegate(Double item)
{
if(! first)
Console.Write(", ");
Console.Write(item);
first = false;
}); |
We find that we have 902 unique numbers generated. You can see the entire list by downloading and executing the code accompanying this article.
Other Uses of Cartesian Products
If we want a true Cartesian product of separate lists we can again use the
CProd.Combinations() method.
Char[]
input1 = new Char[] { 'a', 'b', 'c' },
input2 = new Char[] { 'x', 'y', 'z' },
input3 = new Char[] { 'l', 'm', 'n' };
DisplayResult(CProd.Combinations(input1, input2, input3)); |
To get the following results:
axl
axm
axn
ayl
aym
ayn
azl
azm
azn
bxl
bxm
bxn
byl
bym
byn
bzl
bzm
bzn
cxl
cxm
cxn
cyl
cym
cyn
czl
czm
czn
Here is another interesting use
of a Cartesian products. Any time we encounter a problem where we need to find all possible choices from a group where the group is not modified by the choosing process we can use our
Chooser.Choose() method.
As an example, let's say we wanted to see all the possible ways to combine the two numbers 0 and 1 four times.
Int32[]
input = new Int32[] { 0, 1 };
DisplayResult(Chooser.Choose(input, 4)); |
We end up with the following result (if you are a programmer, this should look somewhat familiar to you because it is all the binary number from 0 to 15):
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Part IV. Permutations
The permutation of a group is basically 'shuffling' the order. There are many problems where we encounter this type of situation, for example:
"The words 'a','b','c', and 'd' are written on pieces of paper and placed in a hat. What are all the possible sequences that the letters could occur as they are picked out of the hat?"
In this case, the source group is changed every time we pick a piece of paper so we are really looking for all the permutations of the group. Again, we can use our utility Combiner functions to help. The recursive
Permute() method below takes the first item in the list and combines it with the remaining items in the list. This ends up giving us all permutations of the list. We need to track the index of the item we are skipping in the list because we may encounter, for example, a
Char[] with two 'a' members and would not want to skip both of them.
public static class Permuter
{
public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> input)
{
Int32 index = 0;
foreach (T item in input)
foreach(IEnumerable<T> grp in Combiner.Combine(item, Permute(Skipper(input, index++))))
yield return grp;
}
private static IEnumerable<T> Skipper<T>(IEnumerable<T> input, Int32 skipIndex)
{
Int32 index = 0;
foreach (T item in input)
if (skipIndex != index++)
yield return item;
}
} |
We can use our new
Permuter methods to easily solve our permutation problem in one line of code.
DisplayResult(Permuter.Permute(new Char[]{ 'a', 'b', 'c', 'd'})); |
This produces the following results:
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
Part V. Wrap-up
As you can see, we can do a lot of manipulation of collections using
IEnumerable<> and a small group of utility methods. Hopefully you'll find these methods helpful in solving problems involving collections. The code attached to this article contains all the utility methods along with the samples.
Until next time,
Happy coding