Disjoint cycles of a permutation

Question

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.
    >> 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


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]

Answer 1

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):

>>> 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:

>>> 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:

>>> 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

>>> from_permutation_to_disjoints_cycles([[1, 2, 3, 4], [2, 3, 1, 4]])
[[1, 2, 3], [4]]

>>> 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:

>>> from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

>>> 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:

>>> from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

>>> 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):

>>> from sympy.combinatorics import Permutation

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

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

Answer 2

How would you get cycles by hand? One is to take the first item (1) and look at what it goes to (3). Then look at what that goes to (2), and see what that goes to (1). Since you got back where you started, you're done with that cycle. Then you go to the first item not in that cycle, and do it again. In pseudo code:

outer loop:
    inner loop:
        find what the current item goes to
        add that to the cycle
        set "current item" to that
        stop when you get to the first item
    add a list containing those items to the list of cycles
    start again with an item you haven't used yet
    keep going until the lists are empty (or only have one item)

In python:

def get_cycles(perm):
    if not is_valid_permutation(perm):
        raise IOError('Input permutation is not valid')
    cycle_list = []
    possible_beginnings= perm[0].copy()
    while True:  
        if len(possible_beginnings)<2:
            break
        start = possible_beginnings[0]
        current = start
        new = perm[1][perm[0].index(start)]
        possible_beginnings.remove(start)            
        if start == new:
            continue     
        cycle = [start,new]    
        current = new
        while True:      
            possible_beginnings.remove(current)
            current = perm[1][perm[0].index(current)]
            if current == start:
                break
            cycle.append(current)  
        cycle_list.append(cycle)
    return cycle_list

I found this to be about twice as fast as your code.

(Note: I used [[1,2,3,4,5,6,7,8,9,10,11,12], [3,1,2,6,5,4,8,9,10,11,12,7]] as my test input, as I figured I should use something a bit larger than the sample you gave, and something with cycles larger than 3.)

Answer 3

Your list flattening is overly complicated. A nice short way to do it is to use itertools.chain:

import itertools

def flatten(x):
    """Flatten a list of lists.
    >>> flatten([[1, 2], [3], [4, 5, 6]])
    [1, 2, 3, 4, 5, 6]
    """
    return list(itertools.chain(*x))

This assumes that there is only one level of nestedness in your list of lists (and exactly one, so it is a bit less general).

It makes up for the loss of generality by being significantly faster:

It has the added benefit, that lift_list crashes when the lists get too large (it worked for len(dc[0]) + len(dc[1]) = 3000 and crashed when trying to go up to 4000).