Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual, I recently found my first edition of the book (although I own the third edition), I felt guilty for not using and started with the much more compact first edition. I do run into errata, but being able to discover it on my own and see it fixed in the new editions, provides a lot of satisfaction :)

One of the commonly used algorithms for combinatorics is ranking and unranking of permutations. The algorithm provided in the book is derived from the Combinatorica package. The book provides an example or two, which is quite terse, so I decided to implement things myself. There is a slightly better explanation in Computational Discrete Mathematics, also written by the same author.

Here is my python implementation of the rank/unrank algorithm(s)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

import functools @functools.lru_cache(maxsize=None) def fact(n): if n == 1 or n == 0: return 1 else: return n*fact(n-1) assert fact(5) == 120 assert fact(0) == 1 #@param perm - given a permutation as an array, calculate it's rank def rank(perm): if not isinstance(perm, list): raise "Invalid input" else: n = len(perm) if n == 0 or (n == 1 and perm[0] == 1): return 0 rest = list(map(lambda x: x - 1 if x > perm[0] else x, perm[1:])) return (perm[0]-1) * fact(n-1) + rank(rest) #@param n, k - given rank k of an n element permutation, print it def unrank(k, n, perm): q, r = divmod(k, fact(n - 1)) perm[0] = q + 1 if n == 1: return [perm[0]] rest = perm[1:] newperm = unrank(r, n - 1, rest) rest = list(map(lambda x: x+1 if x >= perm[0] else x, newperm)) return [perm[0]] + rest

Here are some simple tests and their output

for i in range(24):
    perm=[0 for i in range(4)]
    perm=unrank(i, 4, perm)
    print(perm, "->", rank(perm))

[1, 2, 3, 4] -> 0
[1, 2, 4, 3] -> 1
[1, 3, 2, 4] -> 2
[1, 3, 4, 2] -> 3
[1, 4, 2, 3] -> 4
[1, 4, 3, 2] -> 5
[2, 1, 3, 4] -> 6
[2, 1, 4, 3] -> 7
[2, 3, 1, 4] -> 8
[2, 3, 4, 1] -> 9
[2, 4, 1, 3] -> 10
[2, 4, 3, 1] -> 11
[3, 1, 2, 4] -> 12
[3, 1, 4, 2] -> 13
[3, 2, 1, 4] -> 14
[3, 2, 4, 1] -> 15
[3, 4, 1, 2] -> 16
[3, 4, 2, 1] -> 17
[4, 1, 2, 3] -> 18
[4, 1, 3, 2] -> 19
[4, 2, 1, 3] -> 20
[4, 2, 3, 1] -> 21
[4, 3, 1, 2] -> 22
[4, 3, 2, 1] -> 23

Eyeballing them, they look right to me

Next steps:

Rosetta Code Ranking of Permutations has a comprehensive implementation of ranking/unranking algorithms, including iterative implementations. I would recommend moving to these set as they can be much more performant