Python generate all permutations

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”

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

Источник

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)

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]) 

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.

Источник

Generate all permutations of a List in Python

In this article, we will discuss different ways to get all permutations of elements in a List.

Table Of Contents

Method 1: Using itertools module

The itertools module in Python, provides a function permutations(). It accepts an iterable as argument, and returns a successive r-length permutations of elements in the iterable.

To generate all perumtations of a list, pass the list to the permutations() function as argument, and create a list from the returned values. Let’s see an example,

from itertools import permutations listOfNumbers = [1, 2, 3] # Ger all permutations of a list permutationList = list(permutations(listOfNumbers)) for subList in permutationList: print(subList)

Frequently Asked:

(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)

We create a list of tuples, that contains all the permutations of the original list.

Method 2: Using Custom Function

We can also create a custom function, that accepts a list as argument, and returns a list of lists, containing all the permutations of given list.

def GetPermutations(listOFElements): # Create a empty list of lists listOfLists = [] if len(listOFElements) 
Logic of this function is as follows,

  
Create an empty list of lists to keep the permutations of given list.
  
If the given list is empty. Then it will have no permutations, so return the same empty list only.
  
If the given list has only one element. Then it will have only one permutation, so return the same list.
  
If the list has more than one element, then iterate over all elements by index position. For each element at ith index, 

  
Select the element at ith index in a variable, and select remaining elements in a list.
  
Get permutations of all remaining elements using reccursion, and add ith element to each of it.
  
Add these permutation to list of lists created in first step.

To generate all perumtations of a list, pass the list to our custom function GetPermutations() function as argument, and get a list of lists containing all the permutations. Let’s see a complete example,
def GetPermutations(listOFElements): # Create a empty list of lists listOfLists = [] if len(listOFElements) 
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
 
We create a list of lists, that contains all the permutations of the original list.
 
Summary
 
We learned about two different ways to generate permutations of a list in Python. Thanks.
 
Related posts:
 
Share your love
 
Leave a Comment Cancel Reply
 
This site uses Akismet to reduce spam. Learn how your comment data is processed.
 
Terms of Use
 
Disclaimer
 
Copyright © 2023 thisPointer
 
To provide the best experiences, we and our partners use technologies like cookies to store and/or access device information. Consenting to these technologies will allow us and our partners to process personal data such as browsing behavior or unique IDs on this site and show (non-) personalized ads. Not consenting or withdrawing consent, may adversely affect certain features and functions.
 
Click below to consent to the above or make granular choices. Your choices will be applied to this site only. You can change your settings at any time, including withdrawing your consent, by using the toggles on the Cookie Policy, or by clicking on the manage consent button at the bottom of the screen.
 
The technical storage or access is strictly necessary for the legitimate purpose of enabling the use of a specific service explicitly requested by the subscriber or user, or for the sole purpose of carrying out the transmission of a communication over an electronic communications network.
 
The technical storage or access is necessary for the legitimate purpose of storing preferences that are not requested by the subscriber or user.
 
The technical storage or access that is used exclusively for statistical purposes. The technical storage or access that is used exclusively for anonymous statistical purposes. Without a subpoena, voluntary compliance on the part of your Internet Service Provider, or additional records from a third party, information stored or retrieved for this purpose alone cannot usually be used to identify you.
 
The technical storage or access is required to create user profiles to send advertising, or to track the user on a website or across several websites for similar marketing purposes.
 
Источник
 
Generate All Permutations of a List in Python
 
 
 
Use itertools.permutations to Generate All Permutations of a List in Python
 
Use Recursion to Generate All Permutations of a List in Python
 
 
This tutorial discusses methods to generate all permutations of a list in Python.
 
Use itertools.permutations to Generate All Permutations of a List in Python
 
Python provides a standard library tool to generate permutations: itertools.permutation . The below example shows how to use this to generate all permutations of a list.
 
import itertools inp_list = [4, 5, 6] permutations = list(itertools.permutations(inp_list)) print(permutations) 
 
[(4, 5, 6), (4, 6, 5), (5, 4, 6), (5, 6, 4), (6, 4, 5), (6, 5, 4)] 
 
The default length of the permutation is set to be the length of the input list. However, we can specify the length of the permutation in the itertools.permutations function call. The below example illustrates this.
 
import itertools inp_list = [1, 2, 3] permutations = list(itertools.permutations(inp_list, r=2)) print(permutations) 
 
The below example illustrates how to generate all permutations of all possible lengths of a given list.
 
import itertools inp_list = [1, 2, 3] permutations = [] for i in range(1,len(inp_list)+1):  permutations.extend(list(itertools.permutations(inp_list, r=i))) print(permutations) 
 
[(4,), (5,), (6,), (4, 5), (4, 6), (5, 4), (5, 6), (6, 4), (6, 5), (4, 5, 6), (4, 6, 5), (5, 4, 6), (5, 6, 4), (6, 4, 5), (6, 5, 4)] 
 
Use Recursion to Generate All Permutations of a List in Python
 
We can also use recursion to generate all permutations of a list in Python. The below example illustrates this.
 
def permutations(start, end=[]):  if len(start) == 0:  print(end)  else:  for i in range(len(start)):  permutations(start[:i] + start[i+1:], end + start[i:i+1])  permutations([4,5,6]) 
 
[4, 5, 6] [4, 6, 5] [5, 4, 6] [5, 6, 4] [6, 4, 5] [6, 5, 4] 
 
Related Article - Python List
 
Copyright © 2023. All right reserved
 
Источник