Quick Generation of a Combination Element Using the Combinadic with Python

A combination is a subset of n items taken k at a time. For example, if n = 5 and k = 3, the possible combination elements are:

0: [0 1 2]
1: [0 1 3]
2: [0 1 4]
3: [0 2 3]
4: [0 2 4]
5: [0 3 4]
6: [1 2 3]
7: [1 2 4]
8: [1 3 4]
9: [2 3 4]

The number of combination elements is usually given by what is called the Choose() function. In this case Choose(5,3) is 10.

Now suppose you want to generate a specific combination element, such as element(9) = [2 3 4]. A naive way to do this is to write a next() function that accepts an element and returns the next one. Then you could code up a loop like:

element = [0, 1, 2]
for i in range(10):
  element = next(n, k, element)
print(element)

Unfortunately the number of combination elements gets astronomically large for even moderate sizes of n and k. Some years ago I came up with an algorithm to directly generate the mth combination element for specified n and k. I call the entity the combinadic. My original implementation used the C# language. I decided to code a Python version just for fun.

The Python version has a fatal flaw however. It depends on the scipy comb() function (which is what every mathematician in the universe calls the choose() function) and if n and k are large, comb() will barf out. The solution, which I didn’t code, is to use a Python bignum data type. I demonstrated that approach using C# in an article at https://visualstudiomagazine.com/articles/2012/08/01/biginteger-data-type.aspx.



Artist Jeannette Guichard-Bunel uses interesting combinations of colors, styles, and media.

This entry was posted in Miscellaneous. Bookmark the permalink.