The Permutation Iterator in Python

The permutation is a frequently-used algorithm that we can apply to strings, list, or arrays (vector). In Python, we can import the itertools and use the permutations method which will yield a permutation at a time – note that itertools.permutations works for both strings and list.

1
2
3
4

>>>list(itertools.permutations([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
>>> list(itertools.permutations("123"))
[('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]

>>>list(itertools.permutations([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
>>> list(itertools.permutations("123"))
[('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]

The number of total permutations is N! given the size of N elements in the string or list. For example, there are 6 permutations (3!) for a list of size 3. The fact that we may not need all permutations at once, thus we can use yield keyword that basically turns the function into returning an iterator. The iterator avoids using too much memory and is faster in practical use if you are not intending to check all permutations.

Python Permutation Iterator on List

Based on this permutation algorithm, we can recursively swap in/out the current element at position, and yield any combination result when the index reaches the end.

1
2
3
4
5
6
7
8
9

def permutation_list(items, i = 0):
    if i == len(items):
        yield items
    else:
        for j in range(i, len(items)):
            items[i], items[j] = items[j], items[i]
            for x in permutation_list(items, i + 1):
                yield x
            items[i], items[j] = items[j], items[i]

def permutation_list(items, i = 0):
    if i == len(items):
        yield items
    else:
        for j in range(i, len(items)):
            items[i], items[j] = items[j], items[i]
            for x in permutation_list(items, i + 1):
                yield x
            items[i], items[j] = items[j], items[i]

Calling this permutation function on list [1, 2, 3] gives the iterator that will produce the following if you convert it to list (or simply iterating over the iterator):

1
2
3
4
5
6

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

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

Note that this permutation function does not work for strings, because you simply can’t swap two characters of a string, as the strings in Python are immutable.

Python Permutation Iterator on String

The following Python permutation iterator works for Strings only. We are separating the original string into two: head and tail. Then, recursively append each character into tail until the head is empty – which means a permutation string is being yield.

1
2
3
4
5
6
7

def permutation_string(head, tail = ''):
    if len(head) == 0: 
        yield tail
    else:
        for i in range(len(head)):
            for s in permutation_string(head[0:i] + head[i+1:], tail+head[i]):
                yield s

def permutation_string(head, tail = ''):
    if len(head) == 0: 
        yield tail
    else:
        for i in range(len(head)):
            for s in permutation_string(head[0:i] + head[i+1:], tail+head[i]):
                yield s

Invoke the function on string “123” that gives the following iterator:

1
2
3
4
5
6

123
132
213
231
312
321

123
132
213
231
312
321

Permutation results look organised and are in good order. The function does not work for list as we are using a second parameter (optional) which is initialised to empty string.

Python Permutation Iterator on List and String

Let’s take a look at the following improved iterator, that works for both strings and list.

1
2
3
4
5
6
7

def permutation(items):
    if len(items) <= 1:
        yield items
    else:
        for nextItems in permutation(items[1:]):
            for i in range(len(nextItems) + 1):
                yield nextItems[:i] + items[0:1] + nextItems[i:]

def permutation(items):
    if len(items) <= 1:
        yield items
    else:
        for nextItems in permutation(items[1:]):
            for i in range(len(nextItems) + 1):
                yield nextItems[:i] + items[0:1] + nextItems[i:]

The [0:1] array slicing also works for strings. And the recursive permutation algorithms works by inserting current first (head) item into the other positions. And thus, the permutated results may look random and kinda dis-ordered.

1
2
3
4
5
6

123
213
231
132
312
321

123
213
231
132
312
321

See also: Teaching Kids Programming – Recursive Permutation Algorithm

Permutations and Combinations

• Using Bitmasking Algorithm to Compute the Combinations of an Array
• Teaching Kids Programming – Recursive Backtracking Algorithm to Compute the Combinations
• Teaching Kids Programming – Recursive Permutation Algorithm
• Teaching Kids Programming – Introduction to Permutation and Combination
• Teaching Kids Programming – Three Algorithms to Compute the Combination Number
• A Recursive Full Permutation Algorithm in Python
• The Permutation Iterator in Python
• GoLang: Full Permutation Command Line Tool
• The Permutation Algorithm for Arrays using Recursion
• Full Permutation Algorithm Implementation in BASH

–EOF (The Ultimate Computing & Technology Blog) —