why do you not simple do:
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 🙂