懐中望遠鏡（仮）

Permutation algorithm in Python

In this article, I will introduce permutation algorithms.

Straightforward way

Above steps can be coded by calling function recursively.

def perm(lst, permutation=[]):
    if not lst:
        # if list is empty, finish choosing steps
        print(permutation)

    else:
        # 'for ... in' loop represents each steps
        for chosen in lst:

            # 'rest_list' is a list that doesn't have the element 'chosen'
            rest_list = [item for item in lst if item != chosen]

            # add a element that is chosen in this step
            # ('permutation' has chosen elements before this step)
            chosen_elements = permutation + [chosen]
            
            # go to next step
            perm(rest_list, chosen_elements)


perm([1, 2, 3])

Output:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

More recursive way

As below, looking more carefully, you can find recursive pattern.

perm([])     => []

perm([1])    => [1]
# adding '1' to the result of 'perm([])': [ ]
                                           ^
perm([1, 2]) => [1, 2], [2, 1]
# adding '2' to the result of 'perm([1])': [ 1 ]
                                            ^ ^
perm([1, 2, 3]) => [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
# adding '3' to the result of 'perm([1, 2])': [ 1 , 2 ], [ 2 , 1 ]
                                               ^ ^ ^ ^    ^ ^ ^ ^

I think to separate helper functions (interleave and flatten) let you to understand this algorithm more easily.

Helper functions:

import copy

def interleave(lst, element):
    result = []

    for i in range(len(lst) + 1):
        l = copy.copy(lst)
        l.insert(i, element)
        result.append(l)

    return result


def flatten(lst):
    return sum(lst, [])

Recursive algorithm:

def perm_rec(lst):
    if not lst:
        return [[]]
    else:
        # when 'lst' is '[1, 2, 3]',
        # 'rest_perm' is the result of 'perm_rec([2, 3])'
        rest_perm = perm_rec(lst[1:])

        # interleave '1' into each result of 'perm_rec([2, 3])
        result = flatten([interleave(x, lst[0]) for x in rest_perm])

        return result


print(perm_rec([1, 2, 3]))

Output:

[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

#Python