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$
7
  • $\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$ May 15, 2017 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, 2017 at 19:53
  • $\begingroup$ See here: computationalcombinatorics.wordpress.com/2012/09/10/…. $\endgroup$ May 15, 2017 at 20:00
  • $\begingroup$ Hi Yuval, can you please elaborate because I still have trouble in figuring it out. $\endgroup$
    – Li Wang
    May 17, 2017 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$ May 17, 2017 at 15:36

1 Answer 1

1
$\begingroup$

This is called ranking combinatiorial objects, in this case combinations. Ranking and unranking algorithms exist for various simple combinatorial objects and even a general ranking algorithm exists for arbitrary combinatorial objects given that computing the number of objects matching certain criteria is feasible and there is a total ordering (eg lexicographic ordering).

For combinations, a reference is Algorithms for Unranking Combinations and Other Related Choice Functions, Zbigniew Kokosinski 1995

Assuming a lexicographic ordering among combinations of $K$ from $N$ the following algorithm can be used (which runs in $O(K)$ time assuming binomial computations are cheap):

Assuming the combination is given as an array (item) of length $K$ and where

$$item[0]<item[1]<\dots<item[K-1]$$

and each $0 \leq item[i] \leq N-1$

(If you want the combination in reverse order simply change the algorithm below to match in reverse order and skip last step. Also since your combinations take values between $1$ and $N$ you might want to subtract $1$ from below algorithms, where $item[i]$ is used)

$index = 0$

for $i=1$ to $K$:

____ $c = N-1-item[i-1]$

____ $j = K+1-i$

____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

Note: The algorithm above can be modified to rank combinations with repeated/duplicate elements. Ie

$$item[0] \leq item[1] \leq \dots \leq item[K-1]$$

One needs to replace the counts used to represent combinations with repeated elements instead of binomials which count combinations with unique elements.

$index = 0$

$N \leftarrow N+K-1$

for $i=1$ to $K$:

____ $c = N-1-item[i-1]-i+1$

____ $j = K+1-i$

____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

In essense ranking combinations is a bijection from $N,K$ combinations to natural numbers $0 \dots \binom{N}{K}-1$. This defines a combinatorial number system.

Algorithms above are modified to match my use case (for my combinatorics library Abacus) where combinations take values $0 \dots N-1$ and are non-decreasing. For your use case you can modify them to match wikipedia article.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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