{{ message }}

Instantly share code, notes, and snippets.

# begriffs/cycles.py

Created Mar 27, 2012
Decompose a permutation into disjoint cycles
 def cycles(perm): remain = set(perm) result = [] while len(remain) > 0: n = remain.pop() cycle = [n] while True: n = perm[n] if n not in remain: break remain.remove(n) cycle.append(n) result.append(cycle) return result

### papapon commented Apr 9, 2014

 little mistake line 8 : n = perm[n-1]

### SebastianoF commented Aug 15, 2018 • edited

 Hi, Below how I did it in the repo LABelsToolkit on github. Not sure it is more efficient that the previous solution. I tried (unsuccessfully) to implement it recursively, than I tried (again unsuccessfully) to make only the bottleneck merge_decoupled_permutation recursive. # Auxiliaries: 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 # Main methods: 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]