Ranking and unranking of permutations with duplicates

Question

I'm reading about permutations and I'm interested in ranking/unranking methods.

From the abstract of a paper:

A ranking function for the permutations on n symbols assigns a unique integer in the range [0, n! - 1] to each of the n! permutations. The corresponding unranking function is the inverse: given an integer between 0 and n! - 1, the value of the function is the permutation having this rank.

I made a ranking and an unranking function in C++ using next_permutation. But this isn't practical for n>8. I'm looking for a faster method and factoradics seem to be quite popular. But I'm not sure if this also works with duplicates. So what would be a good way to rank/unrank permutations with duplicates?

Answer 1

I will cover one half of your question in this answer - 'unranking'. The goal is to find the lexicographically 'K'th permutation of an ordered string [abcd...] efficiently.

We need to understand Factorial Number System (factoradics) for this. A factorial number system uses factorial values instead of powers of numbers (binary system uses powers of 2, decimal uses powers of 10) to denote place-values (or base).

The place values (base) are –

5!= 120    4!= 24    3!=6    2!= 2    1!=1    0!=1 etc..

The digit in the zeroth place is always 0. The digit in the first place (with base = 1!) can be 0 or 1. The digit in the second place (with base 2!) can be 0,1 or 2 and so on. Generally speaking, the digit at nth place can take any value between 0-n.

First few numbers represented as factoradics-

0 -> 0 = 0*0!
1 -> 10 = 1*1! + 0*0!
2 -> 100 = 1*2! + 0*1! + 0*0!
3 -> 110 = 1*2! + 1*1! + 0*0!
4 -> 200 = 2*2! + 0*1! + 0*0!
5 -> 210 = 2*2! + 1*1! + 0*0!
6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0!
7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0!
8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0!
9 -> 1110
10-> 1200

There is a direct relationship between n-th lexicographical permutation of a string and its factoradic representation.

For example, here are the permutations of the string “abcd”.

0  abcd       6  bacd        12  cabd       18  dabc
1  abdc       7  badc        13  cadb       19  dacb
2  acbd       8  bcad        14  cbad       20  dbac
3  acdb       9  bcda        15  cbda       21  dbca
4  adbc       10  bdac       16  cdab       22  dcab
5  adcb       11  bdca       17  cdba       23  dcba

We can see a pattern here, if observed carefully. The first letter changes after every 6-th (3!) permutation. The second letter changes after 2(2!) permutation. The third letter changed after every (1!) permutation and the fourth letter changes after every (0!) permutation. We can use this relation to directly find the n-th permutation.

Once we represent n in factoradic representation, we consider each digit in it and add a character from the given string to the output. If we need to find the 14-th permutation of ‘abcd’. 14 in factoradics -> 2100.

Start with the first digit ->2, String is ‘abcd’. Assuming the index starts at 0, take the element at position 2, from the string and add it to the Output.

Output                    String
  c                         abd
  2                         012

The next digit -> 1.String is now ‘abd’. Again, pluck the character at position 1 and add it to the Output.

Output                    String
 cb                         ad
 21                         01

Next digit -> 0. String is ‘ad’. Add the character at position 1 to the Output.

Output                   String
 cba                        d
 210                        0

Next digit -> 0. String is ‘d’. Add the character at position 0 to the Output.

Output String cbad '' 2100

To convert a given number to Factorial Number System,successively divide the number by 1,2,3,4,5 and so on until the quotient becomes zero. The reminders at each step forms the factoradic representation.

For eg, to convert 349 to factoradic,

              Quotient        Reminder       Factorial Representation
349/1            349               0                             0
349/2            174               1                            10
174/3            58                0                           010
58/4             14                2                          2010
14/5             2                 4                         42010
2/6              0                 2                        242010

Factoradic representation of 349 is 242010.

Answer 2

Java, from https://github.com/timtiemens/permute/blob/master/src/main/java/permute/PermuteUtil.java (my public domain code, minus the error checking):

public class PermuteUtil {
 public <T> List<T> nthPermutation(List<T> original, final BigInteger permutationNumber)  {
        final int size = original.size();

        // the return list:
        List<T> ret = new ArrayList<>();
        // local mutable copy of the original list:
        List<T> numbers = new ArrayList<>(original);

        // Our input permutationNumber is [1,N!], but array indexes are [0,N!-1], so subtract one:
        BigInteger permNum = permutationNumber.subtract(BigInteger.ONE);

        for (int i = 1; i <= size; i++) {
            BigInteger factorialNminusI = factorial(size - i);

            // casting to integer is ok here, because even though permNum _could_ be big,
            //   the factorialNminusI is _always_ big
            int j = permNum.divide(factorialNminusI).intValue();

            permNum = permNum.mod(factorialNminusI);

            // remove item at index j, and put it in the return list at the end
            T item = numbers.remove(j);
            ret.add(item);
        }

        return ret;
  }
}

Answer 3

One way is to rank and unrank the choice of indices by a particular group of equal numbers, e.g.,

def choose(n, k):
    c = 1
    for f in xrange(1, k + 1):
        c = (c * (n - f + 1)) // f
    return c

def rank_choice(S):
    k = len(S)
    r = 0
    j = k - 1
    for n in S:
        for i in xrange(j, n):
            r += choose(i, j)
        j -= 1
    return r

def unrank_choice(k, r):
    S = []
    for j in xrange(k - 1, -1, -1):
        n = j
        while r >= choose(n, j):
            r -= choose(n, j)
            n += 1
        S.append(n)
    return S

def rank_perm(P):
    P = list(P)
    r = 0
    for n in xrange(max(P), -1, -1):
        S = []
        for i, p in enumerate(P):
            if p == n:
                S.append(i)
        S.reverse()
        for i in S:
            del P[i]
        r *= choose(len(P) + len(S), len(S))
        r += rank_choice(S)
    return r

def unrank_perm(M, r):
    P = []
    for n, m in enumerate(M):
        S = unrank_choice(m, r % choose(len(P) + m, m))
        r //= choose(len(P) + m, m)
        S.reverse()
        for i in S:
            P.insert(i, n)
    return tuple(P)

if __name__ == '__main__':
    for i in xrange(60):
        print rank_perm(unrank_perm([2, 3, 1], i))

Answer 4

For large n-s you need arbitrary precision library like GMP.

this is my previous post for an unranking function written in python, I think it's readable, almost like a pseudocode, there is also some explanation in the comments: Given a list of elements in lexicographical order (i.e. ['a', 'b', 'c', 'd']), find the nth permutation - Average time to solve?

based on this you should be able to figure out the ranking function, it's basically the same logic ;)