Combinatorial analysis - Enumerator

LogoC#In mathematics, the branch that studies number arrangement is called combinatorial analysis. This a pretty tough exercice in general because one we might think of all possiblilities, all ways numbers can be arranged. For example, try to figure how to arrange p distinct numbers within a bunch of n distinct numbers. Not so easy is it ? Fortunatly, combinatorial analysis gives us powerful tools to solve such problems, and it does not focus on numbers, we can apply the same logic to any list or group of objects. At the end, combinatorial analysis can lead to sophisticated theory such as probability theory which is the logical continuity of combinatorial analysis.

However, as a programmer, one might not be so interested in the theory by itself, but much more in how to implement simple algorithms from this mathematical branch.... In this article, I propose you a simple and powerful way to enumerate all combinaisons of numbers in a list, without repetition (if the given list does not contain any repetition....). To do so, we'll use an interesting interface of C# which names IEnumerator. .NET introduced a new way to enumerate objects within a list. We knew the for loop, and you might know the foreach loop now ! Foreach loops make things more easy to understand and prettier codes. Here, we want to implement a named iterator to make things more straightforward rather than implementing the interface over a new class. It is also the proper way to implement it with parameters. So here it is :

 

Explanations :

  • First declare that we want to implement the IEnumerator interface over a list of integers with IEnumerable<List<int>>. This enumerator is named Combinations and takes two parameters, the list from which we want to create the combinations, and the length of each combination.
  • The enumerator will then loop over each member of the list to construct a combination. If the length of the combination to return is equal to unity (1), then we are done and we can return the number where the enumerator is stopped.
  • Before going to the general case, we might validate that the list we are given is still a valid list. To do so, we check if the next sublist (see next section) is of the size of the combination. If it is, then the combination IS the sublist.
  • In the general case, the combination to return is not completed. Imagine that we want combinations with 10 numbers (over say 1000 numbers), and that we have already a combination with 3 numbers inside. The combination will be then a list of the already chosen 3 numbers, plus a combination of 7 other numbers chosen from the remaining ones. We see here the recursivity !
    List<int> subList = liste.GetRange(i + 1, liste.Count - (i + 1));
    This line means that we want to enumerate through a list of (n-1) numbers where n is the size of the given list in parameter. This means that we do not want to repeat the numbers we've already treated.
    foreach(List<int> next in Combinations(subList, length - 1))
    In the sub-list, we also want to enumerate all possible combinations.

    The combination to return is then the list made from the current number i and the sub-combination named next
    yield return listToReturn;
    Finally, the result is return by the interface with the use of the keywords yield return which means that the current result is returned but this does not end the function. The yield keywords means that the current position in the for loop is kept in memory and the next time the enumerator will be called the enumeration will start from this point.

Leave a Reply

%d bloggers like this: