Return permutations of a string python

Question

why do you not simple do:

Nội dung chính Show

1. Recursive Implementation
2. Iterative Implementation
How do you return all permutations of a string in Python?
What are permutations of a string in Python?
How do you find permutations in Python?
How do you find the permutation of a string?

from itertools import permutations
perms = [''.join(p) for p in permutations(['s','t','a','c','k'])]
print perms
print len(perms)
print len(set(perms))

you get no duplicate as you can see :

 ['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 
'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta',
 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 
'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 
'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 
'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 
'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 
'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 
'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 
'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 
'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 
'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 
'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 
'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']
    120
    120
    [Finished in 0.3s]

In this post, we will see how to list out all permutations of a string in Python.

For example, the string ABC has 6 permutations, i.e., ABC, ACB, BAC, BCA, CBA, CAB.

Practice this problem

In Python, we can use the built-in module itertools to get permutations of elements in the list using the permutations() function.

import itertools

if__name__=='__main__':

s='ABC'

nums= list(s)

permutations= list(itertools.permutations(nums))

# Output: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

print([''.join(permutation) forpermutation inpermutations])

However, we can also write your utility function to generate all permutations of a string. We can do this either recursively or iteratively.

1. Recursive Implementation

The idea is to convert the given string to a character array, and in-place generate all its permutations using backtracking.

We can do this by swapping each of the remaining characters in the string with its first character and generating all the permutations of the remaining characters using a recursive call. This is illustrated in the recursion tree shown below.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# Function to swap two characters in a character array

defswap(ch,i, j):

temp=ch[i]

ch[i]=ch[j]

ch[j]=temp

# Recursive function to generate all permutations of a string

defpermutations(ch,curr_index=0):

ifcurr_index==len(ch) -1:

print(''.join(ch))

for iinrange(curr_index, len(ch)):

swap(ch,curr_index,i)

permutations(ch,curr_index+1)

swap(ch,curr_index,i)

if __name__=='__main__':

s='ABC'

permutations(list(s))

Download Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

Here’s another implementation in Python which doesn’t convert the string to a character array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Recursive function to generate all permutations of a string

defpermutations(remaining, candidate=''):

if len(remaining)==0:

print(candidate)

foriin range(len(remaining)):

newCandidate =candidate+remaining[i]

newRemaining=remaining[0:i]+ remaining[i+1:]

permutations(newRemaining,newCandidate)

if__name__ =='__main__':

s='ABC'

permutations(s)

Download Run Code

Output:

ABC
ACB
BAC
BCA
CBA
CAB

2. Iterative Implementation

The idea is to store the partially generated permutations and then use those partial permutations to generate the final permutations in further iterations. Here’s how the code would look like:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

# Iterative function to generate all permutations of a string in Python

defpermutations(s):

# base case

ifnots:

return []

# create a list to store (partial) permutations

partial= []

# initialize the list with the first character of the string

partial.append(s[0])

# do for every character of the specified string

foriinrange(1, len(s)):

# consider previously constructed partial permutation one by one

# iterate backward

forjin reversed(range(len(partial))):

# remove the current partial permutation from the list

curr= partial.pop(j)

# Insert the next character of the specified string into all

# possible positions of current partial permutation.

# Then insert each of these newly constructed strings into the list

for kinrange(len(curr)+1):

partial.append(curr[:k]+ s[i]+curr[k:])

print(partial,end='')

if __name__=='__main__':

s='ABC'

permutations(s)

Download Run Code

Output:

[‘CAB’, ‘ACB’, ‘ABC’, ‘CBA’, ‘BCA’, ‘BAC’]

The time complexity of the above solutions is O(n.n!) since there are n! permutations for a string of length n, and each permutation takes O(n) time.

Thanks for reading.

Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and help us grow. Happy coding 🙂

How do you return all permutations of a string in Python?

To find all possible permutations of a given string, you can use the itertools module which has a useful method called permutations(iterable[, r]). This method return successive r length permutations of elements in the iterable as tuples.

What are permutations of a string in Python?

A permutation, also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n!

How do you find permutations in Python?

To calculate permutations in Python, use the itertools. permutation() method. The itertools. permutations() method takes a list, dictionary, tuple, or other iterators as a parameter and returns the permutations of that list.

How do you find the permutation of a string?

We can find the count without finding all permutation. Idea is to find all the characters that is getting repeated, i.e., frequency of all the character. Then, we divide the factorial of the length of string by multiplication of factorial of frequency of characters.

programming python Permutation Python Def combination python Find permutation C++ Permutation in string

Return permutations of a string python

1. Recursive Implementation

2. Iterative Implementation

How do you return all permutations of a string in Python?

What are permutations of a string in Python?

How do you find permutations in Python?

How do you find the permutation of a string?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội