0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 11, 2011 at 22:37
  • 1
    $\begingroup$ I guess "Yes, read Knuth" is a little bit like "Yes, read Lang" or "Yes, read Bourbaki", but for computer science? :) $\endgroup$
    – Federico Poloni
    Commented Nov 4, 2011 at 11:20
  • $\begingroup$ 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. $\endgroup$
    – Dimitrije Kostic
    Commented Nov 18, 2011 at 5:21
  • $\begingroup$ 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. $\endgroup$
    – Robert Bryan
    Commented Jan 1, 2012 at 8:17

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Robert Bryan
    Commented Jan 1, 2012 at 8:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .