Decompose a permutation into disjoint cycles

cycles.py

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

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

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]