1
$\begingroup$

This question is extended from this Algorithm to generate integer sets fulfills restrictions, in the answer I learned the formal term of this problem, and the recursive algorithm described in that answer also gives me the desired sequence - as much large numbers located in the front as possible, for example, we will get the following output for $F(7,3,4)$:

  • 4>2>1
  • 3>3>1
  • 3>2>2

So here is the question, given a valid combination, is it possible to get its index in the result set without generating the whole result set and searching for it?

$\endgroup$
  • $\begingroup$ Yes, using the recursive formula. This is similar to mapping a $k$-subset of $\{1,\ldots,n\}$ into a number in the range $0,\ldots,\binom{n}{k}-1$, which has been described a few times on this site. $\endgroup$ – Yuval Filmus May 15 '17 at 19:48
  • $\begingroup$ Hi Yuval, thanks for your comment, can you please give me the link to one of those questions? $\endgroup$ – Li Wang May 15 '17 at 19:53
  • $\begingroup$ See here: computationalcombinatorics.wordpress.com/2012/09/10/…. $\endgroup$ – Yuval Filmus May 15 '17 at 20:00
  • $\begingroup$ Hi Yuval, can you please elaborate because I still have trouble in figuring it out. $\endgroup$ – Li Wang May 17 '17 at 13:40
  • $\begingroup$ As the link shows, ranking and unranking (finding the index given the set and vice versa) essentially reduce to calculating how many solutions there are with given prefix. So, how many solutions there are in total, how many begin with $a$, how many begin with $a>b$, and so on. If you know how to calculate these (switching prefix with suffix it that problem is easier), then you can rank and unrank. See if you understand how this works for $k$-subsets of $\{1,\ldots,n\}$, which you can think of as 0/1 vectors of length $n$ containing exactly $k$ ones. $\endgroup$ – Yuval Filmus May 17 '17 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.