Finding all possible permutations of a given string in python
The itertools module has a useful method called permutations(). The documentation says:
itertools.permutations(iterable[, r])
Return successive r length permutations of elements in the iterable.
If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.
Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.
You'll have to join your permuted letters as strings though.
>>> from itertools import permutations>>> perms = [''.join(p) for p in permutations('stack')]>>> perms
['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']
If you find yourself troubled by duplicates, try fitting your data into a structure with no duplicates like a set
:
>>> perms = [''.join(p) for p in permutations('stacks')]>>> len(perms)720>>> len(set(perms))360
Thanks to @pst for pointing out that this is not what we'd traditionally think of as a type cast, but more of a call to the set()
constructor.
You can get all N! permutations without much code
def permutations(string, step = 0): # if we've gotten to the end, print the permutation if step == len(string): print "".join(string) # everything to the right of step has not been swapped yet for i in range(step, len(string)): # copy the string (store as array) string_copy = [character for character in string] # swap the current index with the step string_copy[step], string_copy[i] = string_copy[i], string_copy[step] # recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1) permutations(string_copy, step + 1)
Here is another way of doing the permutation of string with minimal code based on bactracking.We basically create a loop and then we keep swapping two characters at a time,Inside the loop we'll have the recursion. Notice,we only print when indexers reaches the length of our string.Example:ABCi for our starting point and our recursion paramj for our loop
here is a visual help how it works from left to right top to bottom (is the order of permutation)
the code :
def permute(data, i, length): if i==length: print(''.join(data) ) else: for j in range(i,length): #swap data[i], data[j] = data[j], data[i] permute(data, i+1, length) data[i], data[j] = data[j], data[i] string = "ABC"n = len(string) data = list(string) permute(data, 0, n)