Take the 2-minute tour ×

The following is a simple table that is bound by the binomial coefficient where N is 6 and K is 4. The total number of entries can be calculated as N! / ( K! (N - K)! ). So, 6! / (4! (6 - 4)!) = 15.

1234 1235 1236 1245 1246 1256 1345 1346 1356 1456 2345 2346 2356 2456 3456

What I was trying to figure out some time ago is if someone has published a formula or algorithm to calculate an index to a table entry based upon the underlying value in that table. So, for example, if the number is 1245, then the formula should return the value 3 because it is the 4th entry (1st index in table starts with zero) in the table above. Another example is for 1356, the formula should return 8 since it is the 9th entry in the table.

So, I came up with a fairly efficient algorithm that does this and does not use very much memory. If you are interested, you can read about it in my blog and download the source code:


My question is - am I the first to come up with technique, and has anyone ever found a better formula or algorithm for doing this?

For those wondering why anyone would be interested in doing this, the binomial coefficient provides a way to eliminate duplicate values and is thus more likely to fit a large model into memory. Finding an efficient way to access this table should be useful.

share|improve this question
Briefly, Yes; read Knuth. More generally, do some web searches and ask on a CSTHeory or programming forum. Gerhard "Ask Me About System Design" Paseman, 2011.08.11 –  Gerhard Paseman Aug 11 '11 at 22:37
I guess "Yes, read Knuth" is a little bit like "Yes, read Lang" or "Yes, read Bourbaki", but for computer science? :) –  Federico Poloni Nov 4 '11 at 11:20
Whenever I encounter a sequence of integers I don't recognize, the first place I check is oeis.org, Neil Sloane's online Encyclopedia of Integer Sequences. Many of the entries include formulas and algorithms. It's an invaluable reference. –  Dimitrije Kostic Nov 18 '11 at 5:21
Thanks for the responses. I tried looking for the algorithm and mathematical concept behind it, but did not find it in any of Knuth's texts in "The Art of Computer Programming". I have also done many web searches and could not find it. I think I am the first to publish on how to efficiently convert a k-indexes bounded by the binomial coefficent to the correct entry in a table, which is also the rank. The link to the wikopedia article below describes how to convert between the rank and the corresponding k-indexes, but does not talk about the technique that I disovered. –  Robert Bryan Jan 1 '12 at 8:17

1 Answer 1

Is http://en.wikipedia.org/wiki/Combinatorial_number_system what you are looking for?

share|improve this answer
Thanks for the link. This article talks about how to convert between the rank to the correct k-indexes for a problem bounded by the binomial coefficient. However, it does not describe the technique that I discovered which provides a very fast and efficient way to convert between the k-indexes and the position or rank within a table. It suggests an iterative approach which is much less efficient. –  Robert Bryan Jan 1 '12 at 8:22

Your Answer


