Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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:

http://tablizingthebinomialcoeff.wordpress.com/

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
2  
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
1  
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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.