Disjoint cycles of a permutation
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]