For future reference after the discussion https://codereview.stackexchange.com/questions/201725/disjoint-cycles-of-a-permutation
How to go from Cauchy notation to cyclic notation of a permutation with python
After insights from @Accumulation (working but with extra loop and with no inverse) and @Martin R (not working but with cool insight and inverse), here is what I have got: (it seems to work, but is far from the pythonic-elegance suggested by Martin R).
def permutation_from_cauchy_to_disjoints_cycles(cauchy_perm):
# ...
list_cycles = []
cycle = [cauchy_perm[0][0]]
while len(cauchy_perm[0]) > 0:
first_row_element, second_row_element = cycle[-1], cauchy_perm[1][cauchy_perm[0].index(cycle[-1])]
cycle.append(second_row_element)
cauchy_perm[0].remove(first_row_element)
cauchy_perm[1].remove(second_row_element)
if cycle[0] == cycle[-1]:
if len(cycle) > 2:
list_cycles += [cycle[:-1]]
if len(cauchy_perm[0]) > 0:
cycle = [cauchy_perm[0][0]]
return list_cycles
def permutation_from_disjoint_cycles_to_cauchy(cyclic_perm):
"""
from [[1, 3, 5], [2, 4]]
to [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
"""
pairs = sorted([(a, b) for cycle in cyclic_perm for a, b in zip(cycle, cycle[1:] + cycle[:1])])
return [list(i) for i in zip(*pairs)]
And here is a naive recursive version:
def permutation_from_cauchy_to_disjoints_cycles_recursive(cauchy_perm, list_cycles=[]):
if len(cauchy_perm[0]) == 0:
return list_cycles
cycle = [cauchy_perm[0][0], cauchy_perm[1][0]]
cauchy_perm[0].pop(0)
cauchy_perm[1].pop(0)
while cycle[0] != cycle[-1]:
first_row_element, second_row_element = cycle[-1], cauchy_perm[1][cauchy_perm[0].index(cycle[-1])]
cycle.append(second_row_element)
cauchy_perm[0].remove(first_row_element)
cauchy_perm[1].remove(second_row_element)
if len(cycle) > 2:
list_cycles += [cycle[:-1]]
return permutation_from_cauchy_to_disjoints_cycles_recursive(cauchy_perm, list_cycles=list_cycles)
As a side note, in comments at the link above, it came out the definition of generalised Cauchy notation, where only the elements of a list that are moved are written. E.G. The permutation written in Cauchy notation
[[0,1,2,3,4,5], [0,2,1,3,4,5]]
in generalised Cauchy notation becomes:
[[1,2], [2,1]]
Whose cyclic version is
[1,2]
. The name is justified by the fact that also write other things than numbers. The notation
[['worker 5', 'worker 23'],
['task 5', 'task 23']]
implies that worker 5 and worker 23 swap, and all the other worker stay where they are.
This makes the permutation_from_cauchy_to_disjoints_cycles and permutation_from_disjoint_cycles_to_cauchy one the inverse of the other.
Moreover it turns out to be a better notation when dealing with permutations of large lists of objects.
An element of the generalised Cauchy notation provides an incomplete definition of an element of the symmetric group in a classical sense. What remains is only the orbit of the elements involved in the permutation. Nonetheless, if we consider the definition of group as a group acting on a set - as advocated among others by V.I.Arnold -, then mathematically the Cauchy notation, when considered with the set where the group is acting, still satisfy the definition of group acting on a set. The neutral element of the permutation group acting on range(1000) is [] with the generalised Cauchy notation, instead of [range(1000), range(1000)] with the classical Cauchy notation.