Permutations/Rank of a permutation
A particular ranking of a permutation associates an integer with a particular ordering of all the permutations of a set of distinct items. For our purposes the ranking will assign integers to an ordering of all the permutations of the integers .
For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:
PERMUTATION RANK (0, 1, 2, 3) -> 0 (0, 1, 3, 2) -> 1 (0, 2, 1, 3) -> 2 (0, 2, 3, 1) -> 3 (0, 3, 1, 2) -> 4 (0, 3, 2, 1) -> 5 (1, 0, 2, 3) -> 6 (1, 0, 3, 2) -> 7 (1, 2, 0, 3) -> 8 (1, 2, 3, 0) -> 9 (1, 3, 0, 2) -> 10 (1, 3, 2, 0) -> 11 (2, 0, 1, 3) -> 12 (2, 0, 3, 1) -> 13 (2, 1, 0, 3) -> 14 (2, 1, 3, 0) -> 15 (2, 3, 0, 1) -> 16 (2, 3, 1, 0) -> 17 (3, 0, 1, 2) -> 18 (3, 0, 2, 1) -> 19 (3, 1, 0, 2) -> 20 (3, 1, 2, 0) -> 21 (3, 2, 0, 1) -> 22 (3, 2, 1, 0) -> 23
Algorithms exist that can generate a rank from a permutation for some particular ordering of permutations, and that can generate the same rank from the given individual permutation (i.e. given a rank of 17 produce (2, 3, 1, 0) in the example above).
One use of such algorithms could be in generating a small, random, sample of permutations of items without duplicates when the total number of permutations is large. Remember that the total number of permutations of items is given by which grows large very quickly: A 32 bit integer can only hold , a 64 bit integer only . It becomes difficult to take the straight-forward approach of generating all permutations then taking a random sample of them.
A question on the Stack Overflow site asked how to generate one million random and indivudual permutations of 144 items.
- This task is to
- Create a function to generate a permutation from a rank.
- Create the inverse function that given the permutation generates its rank.
- Show that for the two functions are indeed inverses of each other.
- Compute and show here 4 random, individual, samples of permutations of 12 objects.
- Stretch goal
- State how reasonable it would be to use your program to address the limits of the Stack Overflow question.
- References
- Ranking and Unranking Permutations in Linear Time by Myrvold & Ruskey. (Also available via Google here).
- Ranks on the DevData site.
- Another answer on Stack Overflow to a different question that explains its algorithm in detail.
Python
Python: Myrvold & Ruskey
This is based on the work shown in the paper by Myrvold & Ruskey and has algorithms for the two types of ordering of permutations that they show.
Their algorithm is efficient and pythons transparent use of arbitrary precision integers allows the Stack Overflow questions limits to be used. (Chopped at four rather than a million random samples although function get_random_ranks(144, 1e6) doesn't take long).
<lang python>from math import factorial as fact from random import randrange from textwrap import wrap
def identity_perm(n):
return list(range(n))
def unranker1(n, r, pi):
while n > 0:
n1, (rdivn, rmodn) = n-1, divmod(r, n)
pi[n1], pi[rmodn] = pi[rmodn], pi[n1]
n = n1
r = rdivn
return pi
def init_pi1(n, pi):
pi1 = [-1] * n
for i in range(n):
pi1[pi[i]] = i
return pi1
def ranker1(n, pi, pi1):
if n == 1:
return 0
n1 = n-1
s = pi[n1]
pi[n1], pi[pi1[n1]] = pi[pi1[n1]], pi[n1]
pi1[s], pi1[n1] = pi1[n1], pi1[s]
return s + n * ranker1(n1, pi, pi1)
def unranker2(n, r, pi):
while n > 0:
n1 = n-1
s, rmodf = divmod(r, fact(n1))
pi[n1], pi[s] = pi[s], pi[n1]
n = n1
r = rmodf
return pi
def ranker2(n, pi, pi1):
if n == 1:
return 0
n1 = n-1
s = pi[n1]
pi[n1], pi[pi1[n1]] = pi[pi1[n1]], pi[n1]
pi1[s], pi1[n1] = pi1[n1], pi1[s]
return s * fact(n1) + ranker2(n1, pi, pi1)
def get_random_ranks(permsize, samplesize):
perms = fact(permsize)
ranks = set()
while len(ranks) < samplesize:
ranks |= set( randrange(perms)
for r in range(samplesize - len(ranks)) )
return ranks
def test1(comment, unranker, ranker):
n, samplesize, n2 = 3, 4, 12
print(comment)
perms = []
for r in range(fact(n)):
pi = identity_perm(n)
perm = unranker(n, r, pi)
perms.append((r, perm))
for r, pi in perms:
pi1 = init_pi1(n, pi)
print(' From rank %2i to %r back to %2i' % (r, pi, ranker(n, pi[:], pi1)))
print('\n %i random individual samples of %i items:' % (samplesize, n2))
for r in get_random_ranks(n2, samplesize):
pi = identity_perm(n2)
print(' ' + ' '.join('%2i' % i for i in unranker(n2, r, pi)))
print()
def test2(comment, unranker):
samplesize, n2 = 4, 144
print(comment)
print(' %i random individual samples of %i items:' % (samplesize, n2))
for r in get_random_ranks(n2, samplesize):
pi = identity_perm(n2)
print(' ' + '\n '.join(wrap(repr(unranker(n2, r, pi)))))
print()
if __name__ == '__main__':
test1('First ordering:', unranker1, ranker1)
test1('Second ordering:', unranker2, ranker2)
test2('First ordering, large number of perms:', unranker1)</lang>
- Sample output
First ordering:
From rank 0 to [1, 2, 0] back to 0
From rank 1 to [2, 0, 1] back to 1
From rank 2 to [1, 0, 2] back to 2
From rank 3 to [2, 1, 0] back to 3
From rank 4 to [0, 2, 1] back to 4
From rank 5 to [0, 1, 2] back to 5
4 random individual samples of 12 items:
1 4 5 10 7 3 2 6 9 11 0 8
0 4 9 11 8 10 7 2 6 5 1 3
11 8 2 3 10 7 4 6 1 0 5 9
11 6 7 1 9 5 4 0 2 8 3 10
Second ordering:
From rank 0 to [1, 2, 0] back to 0
From rank 1 to [2, 1, 0] back to 1
From rank 2 to [2, 0, 1] back to 2
From rank 3 to [0, 2, 1] back to 3
From rank 4 to [1, 0, 2] back to 4
From rank 5 to [0, 1, 2] back to 5
4 random individual samples of 12 items:
8 9 4 11 7 0 3 6 1 10 2 5
1 2 0 11 8 6 3 9 4 10 7 5
9 1 4 8 2 10 3 7 0 6 11 5
4 7 11 2 5 0 3 8 9 6 10 1
First ordering, large number of perms:
4 random individual samples of 144 items:
[92, 32, 141, 93, 97, 45, 70, 134, 60, 5, 99, 4, 13, 80, 68, 100, 77,
115, 116, 34, 50, 117, 26, 31, 88, 128, 14, 35, 106, 129, 114, 73,
101, 142, 29, 11, 1, 86, 17, 38, 130, 140, 84, 51, 81, 110, 111, 64,
24, 3, 16, 6, 139, 104, 103, 8, 75, 62, 43, 113, 137, 48, 22, 53, 30,
125, 33, 67, 69, 143, 83, 121, 123, 138, 102, 87, 57, 49, 58, 82, 20,
109, 89, 59, 96, 56, 19, 10, 90, 28, 41, 94, 107, 108, 95, 74, 21, 66,
40, 25, 46, 78, 44, 112, 124, 36, 135, 42, 132, 79, 37, 63, 15, 2, 61,
47, 85, 72, 0, 119, 39, 52, 55, 65, 136, 23, 18, 127, 27, 126, 131,
133, 71, 54, 7, 98, 9, 12, 118, 122, 120, 91, 76, 105]
[36, 141, 8, 114, 28, 42, 32, 40, 75, 134, 72, 106, 78, 107, 43, 83,
0, 13, 41, 48, 66, 4, 98, 136, 34, 35, 46, 92, 15, 135, 17, 79, 22,
118, 95, 137, 81, 121, 60, 74, 110, 33, 80, 14, 62, 125, 3, 56, 115,
49, 27, 1, 7, 84, 20, 64, 47, 140, 124, 119, 143, 23, 93, 87, 25, 12,
69, 105, 68, 112, 10, 44, 101, 138, 99, 51, 127, 52, 122, 61, 21, 108,
117, 39, 2, 85, 53, 130, 120, 18, 16, 109, 126, 103, 113, 5, 82, 19,
73, 45, 58, 102, 129, 54, 96, 31, 57, 97, 65, 133, 59, 132, 88, 30,
89, 86, 9, 116, 71, 142, 77, 94, 104, 63, 37, 139, 70, 131, 11, 111,
123, 128, 24, 76, 90, 29, 6, 38, 100, 26, 55, 91, 50, 67]
[32, 8, 35, 70, 140, 136, 59, 16, 15, 93, 118, 26, 132, 98, 71, 6,
107, 19, 65, 11, 42, 97, 78, 85, 28, 96, 119, 82, 44, 2, 125, 58, 117,
21, 27, 39, 48, 52, 92, 139, 142, 49, 38, 54, 79, 57, 127, 45, 109,
17, 75, 95, 101, 86, 14, 122, 108, 131, 31, 141, 110, 128, 53, 84, 30,
23, 66, 41, 13, 37, 36, 130, 113, 46, 50, 47, 115, 7, 100, 51, 137,
134, 10, 55, 64, 43, 99, 102, 135, 24, 20, 73, 9, 90, 60, 111, 104,
143, 1, 103, 3, 129, 12, 138, 33, 67, 123, 22, 112, 68, 120, 81, 133,
91, 61, 25, 124, 56, 40, 121, 4, 18, 114, 126, 80, 106, 83, 5, 94,
116, 88, 105, 63, 87, 77, 89, 72, 62, 74, 0, 29, 69, 34, 76]
[28, 68, 101, 27, 40, 79, 73, 2, 75, 97, 135, 23, 17, 95, 58, 26, 80,
93, 49, 31, 140, 39, 25, 35, 83, 114, 1, 13, 48, 29, 134, 122, 70, 0,
91, 62, 77, 37, 14, 44, 24, 50, 126, 9, 42, 67, 100, 104, 99, 59, 55,
21, 123, 138, 33, 116, 127, 115, 82, 61, 117, 130, 43, 86, 22, 12, 56,
60, 47, 78, 121, 131, 36, 38, 51, 4, 139, 142, 128, 98, 84, 92, 111,
5, 53, 106, 34, 6, 3, 20, 72, 112, 11, 136, 94, 32, 71, 132, 88, 124,
85, 110, 108, 137, 30, 89, 74, 120, 8, 102, 41, 81, 129, 107, 63, 118,
66, 7, 133, 65, 125, 64, 90, 141, 109, 57, 18, 69, 103, 76, 113, 16,
52, 15, 19, 46, 96, 45, 10, 54, 105, 143, 87, 119]
Python: Iterative
Functions ranker1 and ranker2 can be changed from the recursive form as used in the paper to iterative versions if they are replaced with the following code that yields the same results: <lang python>def ranker1(n, pi, pi1):
if n == 1:
return 0
n1 = n-1
s = pi[n1]
pi[n1], pi[pi1[n1]] = pi[pi1[n1]], pi[n1]
pi1[s], pi1[n1] = pi1[n1], pi1[s]
return s + n * ranker1(n1, pi, pi1)
def ranker2(n, pi, pi1):
result = 0
for i in range(n-1, 0, -1):
s = pi[i]
pi[i], pi[pi1[i]] = pi[pi1[i]], pi[i]
pi1[s], pi1[i] = pi1[i], pi1[s]
result += s * fact(i)
return result</lang>