Disjoint cycles of a permutation 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.
    &gt;&gt; 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) &gt; 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]
The input validation

is_valid_permutation() does not verify if the elements in the two lists
are unique. As an example

is_valid_permutation([[1, 1, 1, 2], [2, 2, 2, 1]])


returns True (and 

from_permutation_to_disjoints_cycles([[1, 1, 1, 2], [2, 2, 2, 1]])


aborts later with a ValueError because some index is not found).
This can for example be fixed by checking 

len(in_perm[0]) == len(in_perm[1]) == len(set(in_perm[0]))


instead of

len(in_perm[0]) == len(in_perm[1])


Restricting the input to lists of integers seems unnecessary to me,
the conversion from the Cauchy notation to cycles works perfectly with arbitrary values (as long as they are hashable):

&gt;&gt;&gt; print(from_permutation_to_disjoints_cycles([["a", "b", "c", "d"], ["b", "a", "d", "c"]]))
[['a', 'b'], ['c', 'd']]


For invalid input, ValueError seems more
appropriate to me, IOError is meant for I/O related failures, such
as reading or writing data.

From Cauchy notation to cycles

decouple_permutation() can be simplified to

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 [list(a) for a in zip(perm[0], perm[1]) if a[0] != a[1]]


the check for perm[0] != perm[1] is not necessary.

However, I would suggest to use a dictionary instead of a list of lists
to store the mappings. Dictionary lookup is much faster than a (linear)
search in a list (what index() does). This leads to the following
implementation:

def from_permutation_to_disjoints_cycles(perm):
    mappings = { a: b for a, b in zip(*perm) if a != b }
    cycles = []
    for a in perm[0]:
        b = mappings.pop(a, None)
        if b is None:
            continue # `a` has already been handled
        cycle = [a]
        while a != b:
            cycle.append(b)
            b = mappings.pop(b)
        cycles.append(cycle)
    return cycles


For each initial value which has not been handled, we build a complete
cycle by dictionary lookups. pop() retrieves the next element of a
cycle and removes the pair from the dictionary, so that it will not be
handled again. Apart from appending to the cycles, no list modifications
are done. 

(Remark: My initial suggestion did not work correctly. This new version
does essentially what the “pseudo code” in Acccumulation's answer
describes. The implementation however is different.)

In my test this was significantly faster for large permutations (benchmark
below).

Finally, your code does not return cycles with a single element:

&gt;&gt;&gt; from_permutation_to_disjoints_cycles([[1, 2, 3, 4], [2, 3, 1, 4]])
[[1, 2, 3]]


As a consequence, the reverse conversion gives not the original permutation:

&gt;&gt;&gt; from_disjoint_cycles_to_permutation([[1, 2, 3]])
[[1, 2, 3], [2, 3, 1]]


With the dictionary approach, this can be fixed by removing the if a != b condition:

def from_permutation_to_disjoints_cycles(perm):
    mappings = { a: b for a, b in zip(*perm) }
    cycles = []
    for a in perm[0]:
        b = mappings.pop(a, None)
        if b is None:
            continue # `a` has already been handled
        cycle = [a]
        while a != b:
            cycle.append(b)
            b = mappings.pop(b)
        cycles.append(cycle)
    return cycles


Now

&gt;&gt;&gt; from_permutation_to_disjoints_cycles([[1, 2, 3, 4], [2, 3, 1, 4]])
[[1, 2, 3], [4]]

&gt;&gt;&gt; from_disjoint_cycles_to_permutation([[1, 2, 3], [4]])
[[1, 2, 3, 4], [2, 3, 1, 4]]


Benchmark

A primitive benchmark, for the permutation which reverses the first 1000
integers (without the input validation):

import time

perm = [[x for x in range(1, 1001)], [x for x in reversed(range(1, 1001))]]

start = time.time()
c = from_permutation_to_disjoints_cycles(perm)
end = time.time()
print((end - start) * 1000)


Result (on a 1,2 GHz MacBook):


Your code: 20 milliseconds,
My code: 0.8 milliseconds.


From cycles to Cauchy notation

The conversion from the Cauchy notation to cycles works with arbitrary
(distinct) integers (or even arbitrary values), but the reverse
conversion assumes that the values are consecutive integers starting
at 1:

&gt;&gt;&gt; from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

&gt;&gt;&gt; from_disjoint_cycles_to_permutation([[2, 3], [5, 6]]))
[[1, 2, 3, 4, 5, 6], [0, 3, 2, 0, 6, 5]


An alternative approach would be to zip() each cycle with a rotation
of itself, to get the list of mapping pairs:

def from_disjoint_cycles_to_permutation(dc):
    """
    from [[1, 3, 5], [2, 4]]
    to   [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    """
    pairs = [(a, b) for cycle in dc for a, b in zip(cycle, cycle[1:] + cycle[:1])]
    return [list(i) for i in zip(*pairs)]


(The transposition method is taken from Transpose list of lists on Stack Overflow.)

Now the reverse conversion works as expected:

&gt;&gt;&gt; from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

&gt;&gt;&gt; from_disjoint_cycles_to_permutation([[2, 3], [5, 6]]))
[[2, 3, 5, 6], [3, 2, 6, 5]]


and the function is not limited to integers anymore.

Using Sympy

The Permutation
class from Sympy provides functions to convert between the
different representations.

Example (the permutations elements are zero-based integers):

&gt;&gt;&gt; from sympy.combinatorics import Permutation

&gt;&gt;&gt; p1 = Permutation([2, 0, 1, 5, 4, 3])
&gt;&gt;&gt; p1.cyclic_form
[[0, 2, 1], [3, 5]]
&gt;&gt;&gt; p1.full_cyclic_form
[[0, 2, 1], [3, 5], [4]]

&gt;&gt;&gt; p2 = Permutation([[0, 2, 1], [3, 5]])
&gt;&gt;&gt; p2.array_form
[2, 0, 1, 5, 4, 3]