Given an element of the permutation group, expressed in Cauchy notation, it is often useful to have it expressed in disjoint cycles (for example to apply the permutation to the keys of a dictionary).
The code below provides a possible answer to the problem: how to go from the Cauchy notation to the disjoint cycle and backward?
What I could not answer is: how to make it more efficient? Should this be made recursive? Why or why not?
E.g. Cauchy notation
p = [[1,2,3,4,5,6], [3,1,2,6,5,4]]
means permute 1 with 3, 3 with 2, 2 with 1 and 4 with 6, leaving 5 alone.
Corresponding disjoint cycles are:
c = [[1,3,2], [4,6]]
I proposed the same code here and here.
def is_valid_permutation(in_perm):
"""
A permutation is a list of 2 lists of same size:
a = [[1,2,3], [2,3,1]]
means permute 1 with 2, 2 with 3, 3 with 1.
:param in_perm: input permutation.
"""
if not len(in_perm) == 2:
return False
if not len(in_perm[0]) == len(in_perm[1]):
return False
if not all(isinstance(n, int) for n in in_perm[0]):
return False
if not all(isinstance(n, int) for n in in_perm[1]):
return False
if not set(in_perm[0]) == set(in_perm[1]):
return False
return True
def lift_list(input_list):
"""
List of nested lists becomes a list with the element exposed in the main list.
:param input_list: a list of lists.
:return: eliminates the first nesting levels of lists.
E.G.
>> lift_list([1, 2, [1,2,3], [1,2], [4,5, 6], [3,4]])
[1, 2, 1, 2, 3, 1, 2, 4, 5, 6, 3, 4]
"""
if input_list == []:
return []
else:
return lift_list(input_list[0]) + (lift_list(input_list[1:]) if len(input_list) > 1 else []) \
if type(input_list) is list else [input_list]
def decouple_permutation(perm):
"""
from [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
to [[1,3], [2,4], [3,5], [4,2], [5,1]]
"""
return [a for a in [list(a) for a in zip(perm[0], perm[1]) if perm[0] != perm[1]] if a[0] != a[1]]
def merge_decoupled_permutation(decoupled):
"""
From [[1,3], [2,4], [3,5], [4,2], [5,1]]
to [[1, 3, 5], [2, 4]]
"""
ans = []
while len(decoupled):
index_next = [k[0] for k in decoupled[1:]].index(decoupled[0][-1]) + 1
decoupled[0].append(decoupled[index_next][1])
decoupled.pop(index_next)
if decoupled[0][0] == decoupled[0][-1]:
ans.append(decoupled[0][:-1])
decoupled.pop(0)
return ans
def from_permutation_to_disjoints_cycles(perm):
"""
from [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
to [[1, 3, 5], [2, 4]]
"""
if not is_valid_permutation(perm):
raise IOError('Input permutation is not valid')
return merge_decoupled_permutation(decouple_permutation(perm))
def from_disjoint_cycles_to_permutation(dc):
"""
from [[1, 3, 5], [2, 4]]
to [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
"""
perm = [0, ] * max(lift_list(dc))
for cycle in dc:
for i, c in enumerate(cycle):
perm[c-1] = cycle[(i + 1) % len(cycle)]
return [list(range(1, len(perm) + 1)), perm]
from_permutation_to_disjoints_cycles([[1, 2, 3], [3, 2, 1]])
→IndexError: list index out of range
\$\endgroup\$ – Gareth Rees Aug 15 '18 at 15:44