1
$\begingroup$

Suppose that $S=\{1,2,...,n\}$ and we are given an integer $r\leq n$.

An $r$-combination of $S$ is obtained by selecting $r$ distinct integers out of the $n$. We order all $r$-combinations for a given $r$ lexicographically. Call the rank of an $r$-combination its rank in this ordering.

I am interested in finding a $r$-combination given $n$, $r$ and the rank.

For example, if $n=10$, $r=5$, rank $=72$, then the answer should be $1, 3, 5, 6, 7$.

How can we compute this efficiently? In particular, can we do this faster than generating the entire enumeration?

$\endgroup$
  • $\begingroup$ This is answered by both answers of Efficiently enumerate all subsets of an ordered set $\endgroup$ – Peter Taylor Apr 9 at 13:36
  • 2
    $\begingroup$ @one, please explain the meaning of $r$ and $rank$. Yes, I am able to guess their meaning and verify that the rank of 1 3 5 6 7 is $\binom 8 3 + \binom 6 2 + 1$, which is indeed $72$. However, it is expect of you to include the explanation so that future readers do not have to guess. It will hep draw answer faster as well. $\endgroup$ – Apass.Jack Apr 9 at 17:03
  • $\begingroup$ @PeterTaylor I am pretty sure that above link doesn't answer my question. Wiki links only tell finding the r-combination for a given rank. $\endgroup$ – one Apr 10 at 2:59
  • $\begingroup$ I think you need to re-read the linked Wikipedia page more slowly. As it currently stands, you don't even need to read all the way to the "Contents" section. $\endgroup$ – Peter Taylor Apr 10 at 6:25
  • $\begingroup$ I think you are mention to "Finding the k-combination for a given number" section in wiki. But it show different result, isn't it? $\endgroup$ – one Apr 10 at 9:45
1
$\begingroup$

I assume that your rank starts at $0$, as this simplifies the code (for me).

The core question you must be able to answer is how many elements there are in a substructure of yours. So in your example, we're ordering combinations lexicographically so we can use the binomial coeffecient to find how many elements there are of our substructures. We'll first try to find the first element of our combination.

Suppose our first element is $x$, then there are $\binom {n-x}{r-1}$ ways the rest of the elements can be chosen. So how do we find $x$? We repeatedly compare our rank to $\binom {n-x}{r-1}$. Is our rank smaller than this, then we must be in this range of sets. Otherwise we subtract this from our rank to skip these sets and try the next $x$.

Once we have found our $x$, we move on to the second element, etc until we are done. Initially we search with $x = 1$, but we increment $x$ after each element found because we want a strictly increasing lexicographically ordered set.

def binom(n, k):
    if k > n: return 0
    if n - k < k: k = n - k
    r = 1
    for d in range(1, k+1):
        r = r*n//d
        n -= 1
    return r

def derank_one(n, r, rank, x):
    while True:
        size = binom(n - x, r - 1)
        if rank < size:
            return x, rank
        if size <= 0:
            raise ValueError("rank is out of range for this set")
        rank -= size
        x += 1

def derank(n, r, rank):
    x = 1
    result = []
    while r > 0:
        x, rank = derank_one(n, r, rank, x)
        result.append(x)
        r -= 1
        x += 1
    return result

And indeed we find that derank(10, 5, 71) == [1, 3, 5, 6, 7] ($71$ because we count starting from $0$).

$\endgroup$
  • $\begingroup$ For time complexity,binom is O(r) , derank_one is O(n * r) and derank is O(r * n * r). Is it right? $\endgroup$ – one Apr 21 at 8:17
  • $\begingroup$ @one binom is indeed $O(r)$. derank_one is $O(r(n - x))$. But derank is $O(r^2(n - r))$. $\endgroup$ – orlp Apr 21 at 15:28

Your Answer

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

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