Generating All Permutations In Python

This post deals with methods to generate all possible permutations in Python, of a given set of elements. We consider numeric elements in an array here and do not consider repetition of the same elements. Hence if there is a repetition of elements in the array, the same permutation may occur twice.

Prerequisites: Basics of loops and conditionals in Python.

Method 1: generate all possible permutations in Python

The Algorithm – Backtracking

The idea is to take up every element in the array and place it at the beginning and for every such case, recursively do the same for a smaller instance of the same array.

For instance, consider the array [1,2,3]

We take 1 as first element, then for the remaining part of the array, we call the same function. This recursion will take 2 as the first element. Then we call the array with the remaining element i.e. 3. In this recursion, this has to be the one and only first element, hence a permutation is printed and control goes back by one recursion depth. Now here, 3 is tried as the first element. Hence, this process continues until we reach the last element and try it as the first element, in the first recursion depth. At the end of that recursion, we will have all possible permutations

Implementation in Python

Consider the following program,

final = list()
def permute(arr,start,end):
    if start==end:
        final.append(list(arr))
        return
    for k in range(start,end+1):
        arr[start],arr[k] = arr[k],arr[start]
        permute(arr,start+1,end)
        arr[start],arr[k] = arr[k],arr[start]

Notice that we keep passing smaller parts of the same array to the same function by modifying the index values and hence generate all possible permutations.

We append all the permutation results into an array final. Note here that we use list(arr) to make sure we are doing a deep copy and not a shallow copy. (Refer to this)

Below is an output printing all permutation for an array [1,2,3,4]. It will have 24 different permutations. While calling the function, we obviously have to pass the array and indexes as 0 and length-1.

Method 2 – In-Built Method – All permutations

Yes, python does have an in-built library function to generate all possible permutations of a given set of elements. The post simply shows the way to use it!

Consider the following program

from itertools import permutations

perms = permutations([1,2,3,4]) 
  for k in list(perms): 
    print k

We import the specific function “permutations” from the itertools library, call the function and print the set of values returned by the function

Given below is the output for the same array [1,2,3,4]

 

Note that although there is an in-built method, understanding the logic behind it and implementing on our own is a good way to practice.

Feel free to leave any sort of feedback, suggestions, doubts below.

One response to “Generating All Permutations In Python”

1. Rakesh Kumar Dash says:

   July 9, 2022 at 7:20 pm

   better approach, why we need to declare res in global

   def permutation(arr,start,end,final=list()):
   if start==end:
   final.append(list(arr))
   return
   for k in range(start,end):
   arr[start],arr[k] = arr[k],arr[start]
   permutation(arr,start+1,end)
   arr[start],arr[k] = arr[k],arr[start]
   return final

   Reply