I have been playing with encryptions and then series that involved permutations. Submitting my Godeh series to the OEIS made me look closer at the permutations that Python produces, and at maybe reducing those permutations to a single integer.
(p.s. Post is best read on a larger than portrait phone screen)
Here are the start of the permutations used in the Godeh series rows:
(0,)
(0, 1)
(1, 0)
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 0, 1)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)
It can be generated by this:
from itertools import permutations, chain
from math import factorial
from typing import Sequence
from pprint import pp
# %% perms in Python generation order
generation_order = []
for width in range(1, 5):
for perm in permutations(range(width)):
print(perm)
generation_order.append(perm)
I truncate at all the perms for four items, but you get the idea - it could extend in this way without limit.
Ordered by...
Successive groups of permutations are for incrementing items permuted. Within each group, of permutations of the same amount of items, the order is lexicographical, i.e. the Python sorted order,
I stared at, and messed around with the ordered perms of four items above, looking for patterns. But lets just confirm the order is sort by width then lexicographical:
wtl = sorted(set(generation_order),
key=lambda x:(len(x), x))
if generation_order == wtl:
print(' == width_then_lexicographical ordering')
else:
print(' != width_then_lexicographical ordering of:')
pp(wtl)
# Prints: == width_then_lexicographical ordering
Ranks
I remembered that I had created a Rank of a permutation task some time ago, (2012), and that there was something "off" with the ranking.
Sure enough the issue was that a rank number gets transformed into a unique permutation, and vice-versa, knowing the start configuration and given any permutation of it then yoy can generate its rank number - But the order of permutations for increasing rank number does not have to be that lexical sort used by Python, and indeed the Myrvold & Ruskey or Trottor & Johnson algorithms I converted to Python are not in lexical order.
So now I know I needed some way to rank and un-rank a lexically ordered set of permutations, as generated by Python.
Something to look at and talk about
Lets assign ranks to Python perms and column headings to make it easier to talk about:
from string import ascii_uppercase
n = 4 # large enough to hopefully show patterns, but not too large
print(' # : ' + ' '.join(char for char in ascii_uppercase[:n]))
for rank, perm in enumerate(permutations(range(n))):
print(f"{rank:>2} : {perm}")
"""
Outputs:
# : A B C D
0 : (0, 1, 2, 3)
1 : (0, 1, 3, 2)
2 : (0, 2, 1, 3)
3 : (0, 2, 3, 1)
4 : (0, 3, 1, 2)
5 : (0, 3, 2, 1)
6 : (1, 0, 2, 3)
7 : (1, 0, 3, 2)
8 : (1, 2, 0, 3)
9 : (1, 2, 3, 0)
10 : (1, 3, 0, 2)
11 : (1, 3, 2, 0)
12 : (2, 0, 1, 3)
13 : (2, 0, 3, 1)
14 : (2, 1, 0, 3)
15 : (2, 1, 3, 0)
16 : (2, 3, 0, 1)
17 : (2, 3, 1, 0)
18 : (3, 0, 1, 2)
19 : (3, 0, 2, 1)
20 : (3, 1, 0, 2)
21 : (3, 1, 2, 0)
22 : (3, 2, 0, 1)
23 : (3, 2, 1, 0)
"""
Patterns
I can't go through the many false trails I had in coming to my result, (there were several), but I finally noticed that The digits in column A stayed the same for 6 successive rows and six is three factorial. Column B stays the same for 2 successive rows i.e. 2! , I guessed 1! for column C and D is what's left.
A lot of deleted code later I found that, kinda, after you pop the first digit out of the starting perm at rank 0, which would be rank // (4 - 1)!; you could take the second digit out using indices using decreasing factorials, but also modulo the decreasing numbers left to index.
Hard to write a textual description of, but I was very chuffed to work out the following on my own:
def nth_perm(initial: Sequence[int], n: int) -> tuple[int]:
init = list(initial)
a = len(initial)
fac_divs = tuple((n // factorial(a - j)) % (a - j + 1)
for j in range(1, a))
return tuple([init.pop(indx) for indx in fac_divs]
+ init)
nth_perm(range(4), 11)
And indeed the nth perm of (0, 1, 2 ,3) produced for n = 11 was (1, 3, 2, 0).
Check
I decided to check my perm-from-rank generator against the Python permutations:
start = range(4)
for i, perm in enumerate(permutations(range(4))):
assert perm == nth_perm(start, i)
Generate ranking from arbitrary perm
This had its own aha moments, and eventually I created the following code generating the rank of the sorted perm:
def s_perm_rank(p: Sequence[int]) -> int:
"""
Ranking of perm p in the sorted sequence of perms of the ints 0 .. len(p)-1
p must be a permutation of the integers 0 .. (len(p)-1)
"""
this = list(p)
a = len(this)
init = list(range(a)) # Perm of rank 0
assert set(this) == set(init), "p must be perm of the ints 0 .. (len(p)-1)"
n, f = 0, a
while this:
f -= 1
n += init.index(this[0]) * factorial(f)
init.remove(this.pop(0))
return n
Roundtrip Check
To check I roundtrip from rank to perm to rank, and also check against the Python permutations ranking
n = 4
init = range(n)
for i, py_perm in enumerate(permutations(range(n))):
s_perm = nth_perm(init, i)
print(f"{i:>2}: {py_perm=} {py_perm==s_perm=} {i==s_perm_rank(s_perm)=}")
Output:
0: py_perm=(0, 1, 2, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
1: py_perm=(0, 1, 3, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
2: py_perm=(0, 2, 1, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
3: py_perm=(0, 2, 3, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
4: py_perm=(0, 3, 1, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
5: py_perm=(0, 3, 2, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
6: py_perm=(1, 0, 2, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
7: py_perm=(1, 0, 3, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
8: py_perm=(1, 2, 0, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
9: py_perm=(1, 2, 3, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
10: py_perm=(1, 3, 0, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
11: py_perm=(1, 3, 2, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
12: py_perm=(2, 0, 1, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
13: py_perm=(2, 0, 3, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
14: py_perm=(2, 1, 0, 3) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
15: py_perm=(2, 1, 3, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
16: py_perm=(2, 3, 0, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
17: py_perm=(2, 3, 1, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
18: py_perm=(3, 0, 1, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
19: py_perm=(3, 0, 2, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
20: py_perm=(3, 1, 0, 2) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
21: py_perm=(3, 1, 2, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
22: py_perm=(3, 2, 0, 1) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
23: py_perm=(3, 2, 1, 0) py_perm==s_perm=True i==s_perm_rank(s_perm)=True
It works!
Tidy
I searched online, read more mathematical articles in and around the subject of permutations and decided to tidy things up with renamings and changes to function arguments. For example, I found that lex is used as a short replacement for lexicographic ordering, and that a perm is usually generated from the integer width of the perm and the rank required, rather than giving the perm of rank 0 and the rank
The final, (?), version is:
#%% Tidy
def lex_perm_unrank(width: int, rank: int) -> tuple[int]:
"""
Generate the lexicographic-permutation of ints 0 .. width-1 of given rank.
Author: Donald S. McCarthy "Paddy3118"
Date: August 2023
"""
initial = list(range(width))
indices = [(rank // factorial(width - j)) % (width - j + 1)
for j in range(1, width+1)]
return tuple(initial.pop(index) for index in indices)
# %% Check
for w in range(7):
for py_rank, py_perm in enumerate(permutations(range(w))):
lex_perm = lex_perm_unrank(w, py_rank)
assert lex_perm == py_perm
print("lex_perm_unrank consistent with Python permutations order.")
# %% Tidier
def lex_perm_rank(p: Sequence[int]) -> int:
"""
Rank of perm p in the lexicographic ordered perms of ints 0 .. len(p)-1
p must be a permutation of the integers 0 .. (len(p)-1)
Author: Donald S. McCarthy "Paddy3118"
Date: August 2023
"""
perm = list(p)
width = len(perm)
initial = list(range(width)) # Perm of rank 0
assert set(perm) == set(initial), \
"p must be a permutation of the integers 0 .. (len(p)-1)"
rank, f = 0, width
while perm:
f -= 1
rank += initial.index(perm[0]) * factorial(f)
initial.remove(perm.pop(0))
return rank
# %% Check both
for w in range(7):
for py_rank, py_perm in enumerate(permutations(range(w))):
lex_perm = lex_perm_unrank(w, py_rank)
lex_rank = lex_perm_rank(lex_perm)
assert lex_perm == py_perm and lex_rank == py_rank
print("lex_perm_rank/unrank consistent with Python permutations order.")
END.
No comments:
Post a Comment