Combining For-Loops: Simplifying Finite Recursion

Often in programming we are interested in dealing with collections of data. In the post Investigating Basic Combinatorics, we looked at the very basics of calculating how many unique combinations of objects we could create with finite choices of objects. Today, we are going to look at putting these combinations together.

Let’s start with a basic numerical problem: What are all the combinations of the set of all digits, tens, and hundreds values of numbers? In other words, what are all the combinations of {0, 1, 2, … , 9}, {0, 10, 20, … , 90}, and {0, 100, 200, … , 900 }?

An approach in C# might look something like this:

class Program
{
  static void Main(string[] args)
  {
    var digits = new List<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    var tens = new List<int> { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
    var hundreds = new List<int> { 0, 100, 200, 300, 400, 500, 600, 700, 800, 900 };

    var combinations = AllCombinationsOf(digits, tens, hundreds);
    foreach (int number in combinations)
    {
      Console.WriteLine(number.ToString());
    }
    Console.ReadLine();
  }

  static List<int> AllCombinationsOf(List<int> digits, List<int> tens, List<int> hundreds)
  {
    var retVal = new List<int>();
    for (int i = 0; i < 10; ++i)
    {
      for (int j = 0; j < 10; ++j)
      {
        for (int k = 0; k < 10; ++k)
        {
          retVal.Add(hundreds[k] + tens[j] + digits[i]);
        }
      }
    }
    return retVal;
  }
}

0
1
2
3
.
.
.
998
999

Notice that there are 1000 results. Thinking about this from a permutative perspective, this makes sense, there are 10 digits, 10 tens, and 10 hundreds to choose from... ie 10 * 10 * 10 = 1000.

A solution like this is useful for doing some quick calculations in a console, but beyond that it's severely limited. First off the method AllCombinationsOf(...) assumes we are always going to have three List inputs. Secondly, the for-loops assume static index counts. The return value is kind of wonky too. It returns to us the sum of all the numbers. Future implementations will likely not require this use case so it is more useful to have a method that returns only value combinations or index combinations.

A better approach will meet the following criteria:

-the number of collections and the magnitude of each collection can be variable
-the implementation of the combinations will be independent of constructing the combinations
-the data type being combined will not be restricted to int

static void Main(string[] args)
{
  var digits = new List<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  var tens = new List<int> { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
  var hundreds = new List<int> { 0, 100, 200, 300, 400, 500, 600, 700, 800, 900 };

  var unknownLists = AllCombinationsOf(new List<List<int>> { digits, tens, hundreds });

  foreach(List<int> combinations in unknownLists)
  {
	Console.WriteLine((hundreds[combinations[0]] + tens[combinations[1]] + digits[combinations[2]]).ToString());
  }
  
  Console.ReadLine();
}

static List<List<int>> AllCombinationsOf<T>(List<List<T>> listOfLists)
{
  var indexCombinations = new List<List<int>>();      

  for(int i = 0; i < listOfLists[0].Count(); ++i)
  {
	var indexes = new List<int>();
	indexes.Add(i);
	GetNextIndexes(listOfLists, indexes, indexCombinations);
  }

  return indexCombinations;
}

static void GetNextIndexes<T>(List<List<T>> listOfLists, List<int> indexes, List<List<int>> indexCombinations)
{
  var currentIndexesCount = indexes.Count();
  if (currentIndexesCount < listOfLists.Count())
  {    
    for(int i = 0; i < listOfLists[currentIndexesCount - 1].Count(); ++i)
    {
      var newIndexes = new List<int>();
      newIndexes.AddRange(indexes);
      newIndexes.Add(i);
      GetNextIndexes(listOfLists, newIndexes, indexCombinations);
    }
  }
  else
  {
    indexCombinations.Add(indexes);
  }
}

The Main method hasn't changed much, except that we are letting it do the summing. In a real-world scenario we would likely have a separate method for this implementation. The real substance of this solution starts with AllCombinationsOf(...). The first thing to note is that the method is now generic and the lists we are evaluating are no longer restricted to int. Next notice that the return type is List>. For this method I've chosen to return lists of indexes instead of lists of objects. That this method is generic and that we are only interested in combining indexes further removes us from the objects, their implementations, or the implementations of the combinations of the objects.

AllCombinationsOf(...) begins by instantiating our return object - an empty List> called indexCombinations. Next we use a for-loop to iterate through each member of the first List in listOfLists. Inside the for-loop a new List called indexes is instantiated to capture a single combination of indexes and the current index of the first List is added to it. Since we don't know how many objects live inside listOfLists, we use recursion to iterate through the remaining lists. Once our indexes variable has a count equal to that of the count of listOfLists, we know we've captured an index from each list in listOfLists. Let's look at this method a little closer.

First, we'll get the count of the current combination of indexes. If the currentIndexesCount is less than the listOfLists count, then we will iterate through next List in listOfLists, which will have the same index as the currentIndexesCount - 1. This is not much different than the very first list we iterated, except now we have some additional variables to track which List we are iterating. The for-loop inside is almost identical as well, except that when we instantiate a new set of indexes, we copy the indexes from the previous for loops into our new set. Referring back to the concrete example from earlier, for each of the 10 hundreds, 10 tens, and 10 digits, a new set of indexes will be instantiated - ie 1000 set of indexes.

The recursion is terminated when the count of the current indexes equals the count of the listOfLists. When this condition is met, the current indexes combination is added to indexCombinations. Since each list is iterated fully against each other list the return value gives us every combination possible of each index from each list.

As anticipated the output in the console is the same as before, except now we have a strategy that offers flexibility and reuse.