Ranking and Unranking of Combinations and Permutations

by Derrick Stolee

Now that we’ve discussed a nice standard example of canonical deletion, I want to get into more complicated uses. These techniques use more complicated augmentations and deletions, and hence require a little more delicate description of orbit calculations. In order to get to those, we need to be able to store and manipulate subsets of things. Another way to think of “subsets of things” is combinations, especially when we know the size of the subset.

Given a set X, we will discuss the power set 2^X of all subsets of X, the k-subsets \binom{X}{k}, the k-tuples X^k, and the k-permutations (X)_k. There are multiple ways to store a given subset, tuple, or permutation, but what is more important is how to store a list of information over the entire collection of these objects. My favorite method is to use a ranking function, which assigns each object an integer which I can use as an array position. Then, an unranking function will invert this process.

This area has a long history, with several different methods of ranking and unranking the objects competing for dominance in several measures of quality. My favorite measure is “readability” and/or “ease of programming” but definitely “computation speed” is important, too. However, sometimes ranking is fast and unranking is slow, sometimes the ranking and unranking is fixed to a certain order, such as lexicographic order.

Today we’ll talk about several ranking and unranking procedures, and the next post will discuss how to use these ranking/unranking functions to compute orbits of these objects for a graph with symmetry.

Since we will be dealing with actual software implementations of these combinatorial objects, we shall use the following conventions:

  1. [n] = \{0,1,\dots,n-1\}.
  2. For S \in 2^{[n]}, S[i] is the ith element of S, for i \in [|S|].

Ranking Subsets

Subsets are some of the easiest objects to rank, since there is a very simple bijection between the subsets of [n] and the first 2^n integers. For a subset S \in 2^{[n]}, let m_S be the n-bit integer whose ith coordinate is the indicator with value 1 if and only if i \in S. The best part about this ranking is that the integer rank is the set, stored directly. To test membership of i in S using m_S, simply test if (m_S \& (1 \ll i)) \neq 0.

Of course, actually ranking all subsets is not recommended for large n, but particularly when n is near the number of bits in a standard-length integer (32 or 64, depending on your processor/language). Even using that last bit can cause sign errors if you’re not careful!

Ranking Tuples

To rank tuples, consider the simplest way to count k-tuples in [n]: there are n ways to fix the ith coordinate and n^{i} ways to extend the tuple to the previous positions (recall i \in [k] = \{0,\dots,k-1\}). Therefore, we can rank a tuple {\mathbf x} \in [n]^k by {\mathrm{rank}}({\mathbf x}) = \sum_{i=0}^{k-1} x_i n^{i}. To unrank the tuple, iteratively pull out the residue modulo n and then divide by n (using integer division) to find the rank of the remaining tuple of shorter length.

In the special case that n = 2^m, we can assign each block of m bits to be the value x_i with the same ranking function but a faster unranking procedure (it avoids integer division). In fact, you could use a similar approach for all n \leq 2^m, except there will be integers which do not correspond to tuples. This may be trivial when both k and m are small, but the effect grows exponentially with k with base 2^m - n.

Ranking Combinations

Lexicographic Order

The most natural way to order combinations of [n] is lexicographically. This is the same way we order words in a dictionary. So, S <_{\text{lex}} T if S[i] = T[i] for all i < \ell < k and S[\ell] < T[\ell]. Hence the first k-set is \{0,1,\dots,k-1\} and the last is \{n-k,n-k+1,\dots,n-1\}. However, the set \{0,1,\dots, k-2, n-1\} is before the set \{0,2,3,\dots,k-1,k-2\}.

This ordering provides a natural ranking procedure:

{\mathrm{rank}}_{\text{lex}}(S) = \sum_{i=0}^{k-1} \sum_{v=S[i-1]+1}^{S[i]-1}\binom{n-(v+1)}{k-(i+1)}.

The idea of this ranking is that we go through all of the positions i \in \{0,\dots,k-1\} and compute how many k-sets start with the first i positions of S, then have the value v, then any (k-i-1)-set of elements from \{v + 1, \dots, n - 1 \}. To unrank, we find the positions in increasing order by subtracting these inner sum values, when possible.

unranklex(n, k, m):
    S \leftarrow [k]
    i \leftarrow 0
    t \leftarrow 0
    while i < k:
        v \leftarrow \binom{n-1-t}{k-i-1}
        if v \leq m:
            m \leftarrow m - v
        else
            S[i] \leftarrow t
            i \leftarrow i + 1
        t \leftarrow t + 1
    return S

This ranking function is unfortunate that it requires the nested sums (and the binomial requires a loop to calculate, as well). By changing the order slightly, we can improve performance.

Co-Lex Order

Using the co-lexicographic ordering of the combinations can simplify a few things. First, the dependence on n will be completely removed. Second, the ranking and unranking methods are much simpler. The co-lex order is given by comparing the elements of the sets from largest to smallest, until there is a difference. So, S i > \ell and S[\ell] < T[\ell].

To rank a set S in co-lex, we count how many subsets appear before S by using the following fact: the value \ell can appear in the ith position of S only after all i+1-subsets of [\ell] appear as the first i+1 positions of a set, followed by S[i+1], \dots, S[k-1].

{\mathrm{rank}}_{\text{co-lex}}(S) = \sum_{i=0}^{k-1} \binom{S[i]}{i+1}.

To un-rank an index m, we must find the most extremal way to write m as a sum of binomial coefficients, placing the largest value in the top of the coefficient of largest value.

unrankco-lex(k, m):
    S \leftarrow [k]
    i \leftarrow k-1
    while i \geq 0:
        \ell \leftarrow i
        while \binom{\ell}{i+1} \leq m:
            \ell \leftarrow \ell + 1
        S[i] \leftarrow \ell - 1
        m \leftarrow m -\binom{\ell-1}{i+1}
        i \leftarrow i - 1
    return S

Ranking Permutations

You know what? I started this post two weeks ago and delayed writing because I’ve never ranked or unranked a permutation. Apparently, it’s not a simple task. See the references below by Er and Myrvold & Ruskey who present a very detailed bibliography on the techniques here. Also, see Glenn Tesler’s presentation on ranking, unranking, and finding sequential permutations.

Signed Objects

A signed object is usually a pairing of a standard (unsigned) object (such as the objects above) and associating a positive or negative value to each element or position in that object. For example, a signed permutation is really a pair (\pi,\sigma) where \pi : [n]\to[n] is a bijection and \sigma : [n] \to \{+1,-1\} is a function. One simple way to rank such objects is to take a tensor product of the rank of the unsigned object with the rank of the set of elements with negative sign. It only matters which object is “first” in this order. So one option is {\mathrm{rank}}(\pi, \sigma) = 2^n{\mathrm{rank}}(\pi) + {\mathrm{rank}}(\sigma) and another is {\mathrm{rank}}(\pi,\sigma) = n!{\mathrm{rank}}(\sigma) + {\mathrm{rank}}(\pi).

References

J. Arndt, Matters Computational: Ideas, Algorithms, Source Code. Available on the FXT page.

T. Johnston, Sorting Signed Permutations Using Cut-And-Paste Operations, UNL Honors Thesis (2009).

M. C. Er, Lexicographic Enumeration, Ranking, and Unranking of Permutations of r out of n Objects, International Journal of Computer Mathematics 23(1) (1987).

W. Myrvold, F. Ruskey, Ranking and Unranking Permutations in Linear Time, Information Processing Letters (2000).