Generate All Permutations of a Set in Python

Permutations refer to arranging the members of a set into different sequences. if the set is already ordered, rearranging (reordering) its elements. If a set has n elements, the total number of permutations is n! (factorial of n)

Some common approaches we can use to generate all permutations of a set in Python are as follows.

• Using a for loop

• Using itertools.permutations() function.

• Using permutations() in extend() function.

Using 'for' loop Method

This method generates permutations iteratively by using loops. The basic idea is to select each element and then look for permutations of the remaining elements.

Following are the steps involved in generating permutations using loops, if a list has more than one element.

• Loop through each element in the list.

• For each element, remove it from the list and recursively generate permutations of the remaining elements.

• Combine the selected element with each of the generated permutations.

Example

The following example demonstrates generating the permutations iteratively, using loops.

def permutFunc(myList):
   
   # No p ermutations for empty list
   if len(myList) == 0:
      return []
   # Single permutation for only one element
   if len(myList) == 1:
      return [myList]
   
   # Permutations for more than 1 characters
   k = []
   for i in range(len(myList)):
      m = myList[i]
      res = myList[:i] + myList[i+1:]
      for p in permutFunc(res):
         k.append([m] + p)
   return k
myList = list('456')
for p in permutFunc(myList):
   print (p)

Output

The output for the example code above is shown below.

['4', '5', '6']
['4', '6', '5']
['5', '4', '6']
['5', '6', '4']
['6', '4', '5']
['6', '5', '4']

Using 'itertools.permutations()' Function

The itertools.permutations() function is a built-in tool that generates all possible permutations of a given sequence, such as a list or tuple.

The steps involved to generate all the possible permutations of a, using itertools.permutations() function are as follows.

• Utilize itertools.permutations() with the desired iterable (like a range or list).

• Convert the resulting permutations object into a list for easy display.

Example

In this example, the permutations for range (1, 3) are generated. The function list(permutations(...)) takes these arrangements, which are initially created as an iterable object from the itertools.permutations function, and transforms them into a regular list.

from itertools import permutations

# Using the permutations() method
myList = list(permutations(range(1, 4)))

# Display the Permutations
print("Permutations\n",myList)

Output

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

Extending Permutations with itertools

This method involves using the extend() function to collect all permutations of different lengths. Instead of generating permutations of the entire set, by using this approach we can generate permutations of length.

The steps to generate all possible permutations using the extend() and itertools.permutations() functions are as follows.

• Loop through a range from 1 to the length of the list.

• For each iteration, generate permutations of that length using itertools.permutations().

• Combine all these smaller permutations into a single result list using the extend() method.

Example

In the below example, by using extend() method along with itertools.permutations() permutations of different lengths are generated.

import itertools
myList = [2,3,4]
resList = []

for i in range(1,len(myList)+1):
   resList.extend(list(itertools.permutations(myList, r=i)))

# Display the Permutations
print("Permutations\n",resList)

Output

Permutations
 [(2,), (3,), (4,), (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3), (2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2)]