Anonymous user
Permutations/Rank of a permutation: Difference between revisions
→Python: Trotter-Johnson
Line 1,448:
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]</pre>
===Python: Trotter-Johnson===
This uses the Trotter-Johnson permutations generator in which successive permutations differ by only one swap between two items.<br>
Permutations with small differences in rank are likely to be "similar" in appearance (if rank difference << perm length).
<lang python>from random import randrange
from typing import List
Perm = List[int]
_fact = [1] # factorials cache
def print_perm(T: Perm) -> None:
print(T)
def tj_unrank(n: int, r: int) -> Perm:
"Returns the r-ranked Trotter-Johnson permutation of integers 0..n-1"
global _fact
for i in range(len(_fact), n+2): # Extend factorial cache if necessary.
_fact.append(_fact[i - 1] * i)
pi: Perm = [0] * (n+2)
pi[1] = 1
r2 = 0
for j in range(2, n+1):
r1 = (r * _fact[j]) // _fact[n]
k = r1 - j*r2
if ((r2 % 2) == 0):
for i in range(j-1, j - k - 1, -1):
pi[i+1] = pi[i]
pi[j-k] = j
else:
for i in range(j - 1, k, -1):
pi[i+1] = pi[i]
pi[k + 1] = j
r2 = r1
return [i - 1 for i in pi[1:-1]]
def tj_rank(p: Perm) -> int:
"Returns the ranking of the Trotter-Johnson permutation p, of integers 0..n-1"
n = len(p)
assert set(p) == set(range(n)), f"Perm {p} not a perm of 0..{n-1}."
pi = [0] + [i+1 for i in p] + [0]
r = 0
for j in range(2, n + 1):
i = k = 1
while pi[i] != j:
if (pi[i] < j):
k += 1
i += 1
if ((r % 2) == 0 ):
r = j*r+j-k
else:
r = j*r+k-1
return r
def tj_parity(p: Perm) -> int:
"Returns the 0/1 parity of the Trotter-Johnson permutation p, of integers 0..n-1"
n = len(p)
assert set(p) == set(range(n)), f"Perm {p} not a perm of 0..{n-1}."
pi = [0] + [i+1 for i in p] + [0]
a, c = [0] * (n + 1), 0
for j in range(1, n+1):
if a[j] == 0:
c += 1
a[j] = 1
i = j
while ( pi[i] != j ):
i = pi[i]
a[i] = 1
return (n-c) % 2
def get_random_ranks(permsize, samplesize, fact):
perms = fact[permsize]
ranks = set()
while len(ranks) < samplesize:
ranks |= set( randrange(perms)
for r in range(samplesize - len(ranks)) )
return ranks
if __name__ == '__main__':
n = 3
print(f"Testing rank/unrank n={n}.\n");
for i in range(len(_fact), n+2): # Extend factorial cache if necessary.
_fact.append(_fact[i - 1] * i)
for r in range(_fact[n]):
p = tj_unrank(n, r)
rank = tj_rank(p)
parity = tj_parity(p)
print(f" Rank: {r:4} to perm: {p}, parity: {parity} back to rank: {rank}")
for samplesize, n2 in [(4, 12), (3, 144)]:
print('\n %i random individual samples of %i items:' % (samplesize, n2))
for i in range(len(_fact), max([n, n2])+2): # Extend factorial cache if necessary.
_fact.append(_fact[i - 1] * i)
for r in get_random_ranks(n2, samplesize, _fact):
p = tj_unrank(n2, r)
rank = tj_rank(p)
parity = tj_parity(p)
print(f" Rank: {r:10} to perm: {p}, parity: {parity} to rank: {rank:10}")</lang>
{{out}}
<pre>Testing rank/unrank n=3.
Rank: 0 to perm: [0, 1, 2], parity: 0 back to rank: 0
Rank: 1 to perm: [0, 2, 1], parity: 1 back to rank: 1
Rank: 2 to perm: [2, 0, 1], parity: 0 back to rank: 2
Rank: 3 to perm: [2, 1, 0], parity: 1 back to rank: 3
Rank: 4 to perm: [1, 2, 0], parity: 0 back to rank: 4
Rank: 5 to perm: [1, 0, 2], parity: 1 back to rank: 5
4 random individual samples of 12 items:
Rank: 224379355 to perm: [7, 8, 3, 6, 4, 2, 10, 11, 9, 0, 5, 1], parity: 1 to rank: 224379355
Rank: 23097790 to perm: [7, 4, 10, 6, 0, 1, 3, 9, 8, 5, 11, 2], parity: 0 to rank: 23097790
Rank: 117958174 to perm: [0, 8, 7, 3, 6, 10, 2, 5, 9, 1, 11, 4], parity: 0 to rank: 117958174
Rank: 346706871 to perm: [5, 6, 10, 11, 9, 1, 4, 2, 3, 0, 7, 8], parity: 1 to rank: 346706871
3 random individual samples of 144 items:
Rank: 1651131773176615172744310076827657815133816254912906616309984015339196892250696046235920824910965887990997355014521316450705028487598467582997576624750079968277864250809611544676914954500478455362854192561093676053999830054190363254701022398791125041 to perm: [59, 73, 41, 108, 64, 40, 98, 4, 65, 67, 126, 88, 76, 29, 110, 70, 54, 122, 0, 7, 92, 10, 139, 141, 137, 37, 131, 119, 94, 18, 143, 129, 42, 95, 136, 20, 8, 74, 96, 113, 63, 85, 55, 115, 61, 116, 2, 22, 17, 124, 72, 128, 66, 86, 15, 123, 47, 32, 118, 112, 71, 24, 44, 69, 105, 49, 39, 9, 19, 107, 121, 97, 57, 114, 77, 51, 52, 56, 142, 68, 13, 109, 101, 27, 117, 60, 16, 106, 91, 45, 111, 79, 35, 33, 75, 135, 89, 34, 26, 134, 62, 125, 120, 38, 31, 102, 12, 93, 130, 43, 14, 90, 46, 50, 127, 99, 103, 1, 48, 84, 87, 133, 25, 104, 5, 6, 23, 3, 83, 100, 80, 58, 138, 132, 140, 81, 21, 53, 36, 78, 11, 82, 30, 28], parity: 1 to rank: 1651131773176615172744310076827657815133816254912906616309984015339196892250696046235920824910965887990997355014521316450705028487598467582997576624750079968277864250809611544676914954500478455362854192561093676053999830054190363254701022398791125041
Rank: 1139027037513751332871831142078907765417112324514533855069759708279338770804249106066012939576097376526053338448990932324347478214081719932920707580823619461100977982441090762742918774404245754930272491547901228595855393218252364279122306190572350742 to perm: [16, 104, 135, 22, 134, 88, 112, 141, 76, 86, 29, 11, 82, 28, 87, 57, 92, 73, 77, 46, 43, 137, 65, 54, 58, 125, 40, 83, 108, 18, 84, 60, 133, 99, 48, 98, 62, 55, 37, 70, 66, 91, 126, 113, 90, 45, 118, 89, 69, 68, 115, 117, 4, 53, 3, 21, 5, 33, 105, 95, 36, 0, 85, 27, 78, 142, 101, 94, 39, 131, 138, 120, 121, 41, 67, 136, 109, 32, 2, 128, 52, 8, 96, 44, 139, 132, 81, 123, 122, 129, 75, 35, 114, 59, 102, 12, 10, 93, 124, 56, 34, 50, 80, 7, 140, 38, 49, 6, 127, 24, 42, 106, 71, 97, 116, 23, 15, 30, 103, 20, 51, 143, 14, 1, 107, 64, 130, 9, 47, 17, 72, 19, 13, 119, 74, 79, 61, 111, 110, 26, 100, 25, 31, 63], parity: 0 to rank: 1139027037513751332871831142078907765417112324514533855069759708279338770804249106066012939576097376526053338448990932324347478214081719932920707580823619461100977982441090762742918774404245754930272491547901228595855393218252364279122306190572350742
Rank: 714995631345946967042806483133964554958984960300330719707047323701281032269403416575046138945880520006134289348162836428854957729363688052297494097936794838200697086588398613171177193379516938048929841183345138224064281691610834904263581078991507944 to perm: [53, 123, 58, 38, 126, 23, 43, 137, 18, 42, 118, 107, 130, 68, 31, 84, 11, 4, 125, 83, 122, 117, 82, 12, 59, 94, 90, 112, 98, 104, 124, 128, 120, 88, 91, 93, 6, 108, 115, 143, 44, 56, 73, 136, 14, 134, 54, 105, 7, 16, 97, 127, 9, 66, 37, 113, 3, 67, 102, 57, 106, 76, 19, 100, 49, 101, 74, 96, 95, 32, 35, 77, 142, 103, 70, 141, 135, 72, 129, 65, 46, 89, 51, 25, 40, 131, 24, 5, 21, 34, 10, 99, 55, 71, 114, 139, 87, 75, 64, 133, 45, 63, 48, 132, 29, 92, 22, 86, 20, 41, 33, 85, 138, 17, 0, 28, 119, 36, 79, 111, 80, 116, 30, 15, 61, 60, 1, 52, 121, 2, 62, 69, 13, 109, 78, 81, 110, 47, 26, 39, 27, 140, 50, 8], parity: 0 to rank: 714995631345946967042806483133964554958984960300330719707047323701281032269403416575046138945880520006134289348162836428854957729363688052297494097936794838200697086588398613171177193379516938048929841183345138224064281691610834904263581078991507944</prre>
===Python: Iterative===
| |||