How to generate all Permutations of a List

In this article, we will learn how to generate all possible permutations of a list in Python. We will use some built-in functions and some custom codes as well. Let's first have a quick look over what is a list and what is permutation in Python.

Python List

Python has a built-in data type called list. It is like a collection of arrays with different methodology. Data inside the list can be of any type say, integer, string or a float value, or even a list type. The list uses comma-separated values within square brackets to store data. Lists can be defined using any variable name and then assigning different values to the list in a square bracket. The list is ordered, changeable, and allows duplicate values. For example,

list1 = ["Ram", "Arun", "Kiran"]
list2 = [16, 78, 32, 67]
list3 = ["apple", "mango", 16, "cherry", 3.4]

We all have heard and studied the permutation concept in mathematics, likewise, Python supports some built-in functions to generate permutations of a list. Python provides a standard library tool to generate permutations by importing itertools package to implement the permutations method in python. We will also discuss the recursive method to generate all possible permutations of a list.

Example Generate Permutations of a list

The below example passes the given list as an argument to itertools.permutations() function. It defaults to the length of the list and hence generates all possible permutations.

import itertools

list1 = [1, 2, 3]

perm = list(itertools.permutations(list1))

print(perm)

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

Example: Generate successive 'r' length permutations of a list

The below example passes the given list and length as an argument to itertools.permutations() function. It generates the permutations of the given length.

import itertools
list1 = [1, 2, 3]
r = 2
perm = list(itertools.permutations(list1, r))
print(perm)

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

Example: Generate Permutations of a list

The below example takes an empty list to store all permutations of all possible length of a given list. extend() function is used to add items to the empty list one after the other. Iterating over the elements of the list using for loop, the itertools.permutations() function finds all the possible lengths.

import itertools

list1 = [1, 2, 3]

perm = []

for i in range(1,len(list1)+1):
    perm.extend(list(itertools.permutations(list1, r=i)))
print(perm)

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

Example: Recursion method to generate all permutations of a list

The below example uses recursion to generate all permutations of a list. It defaults to the length of the list and hence generates all possible permutations.

def perm(start, end=[]):
    if(len(start) == 0):
        print(end)
    else:
        for i in range(len(start)):
            perm(start[:i] + start[i+1:], end + start[i:i+1])
            
#function call
perm([1,2,3])

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

Conclusion

In this article, we learned to generate all possible permutations of a list by using itertools.permutations() function and recursive method. We discussed them with different examples.