Kodeclik Blog
Find all permutations of a given string in Python
At some point in your Python journey, you will come across the need to find all possible permutations of a given string. Perhaps you are looking to create passwords out of a set of characters and want to explore different variations and choose the best one. Alternatively maybe you are looking to solve an anagram game and trying to see if there are anagrams of a given word that are also meaningful English words. One way to do this is to generate all permutations and compare them against a dictionary of legal English words.
If a string has n characters, the number of permutations is: n! (n factorial, or n * (n-1) * (n-2) * and so on, all the way to 1). This can become daunting as n increases and it is not easy to write such a program if we are not being systematic or clever about it.
For instance, for the given string “kode”, because it is of length 4, there are 4*3*2*1 = 24 permutations, described in the following list of strings:
['kode', 'okde', 'odke', 'odek', 'kdoe', 'dkoe', 'doke', 'doek',
'kdeo', 'dkeo', 'deko', 'deok', 'koed', 'oked', 'oekd', 'oedk',
'keod', 'ekod', 'eokd', 'eodk', 'kedo', 'ekdo', 'edko', 'edok']You can verify that no string is missing and that there are no duplicates. Let us explore two ways to write such a program!
Method 1: Write a recursive program to find all permutations of a given string
The first approach we will take is to write a function to insert a given character at every position in a given string and then to call this function repeatedly using recursion.
Let us write a function called “insert_char” that takes a single character (stored in c) and a string (s), and inserts c at every possible position in s; thus returning a list of strings. Note that if the string is of length x, there are x+1 possible positions to insert the character.
Below is the desired function:
def insert_char(c, s):
insertions = []
insertions.append(c + s)
for (i, x) in enumerate(s):
t = s[0:i + 1] + c + s[i + 1:len(s)]
insertions.append(t)
return (insertions)The insertions list contains the possible insertions that are systematically accumulated in the program. We use the Python enumerate function to iteratively obtain all the indices and use these indices to split the string into left and right pieces and insert the desired character in between the left and right substrings. In addition we prepend the desired character to obtain another variant.
If the program is run for instance like:
print(insert_char('$','kode'))we will get:
['$kode', 'k$ode', 'ko$de', 'kod$e', 'kode$']as expected.
Next, we will use the above function in a recursion to generate all the permutations:
def permute(s):
permutations = []
if (len(s) == 0):
return(permutations)
elif (len(s) == 1):
permutations.append(s)
return (permutations)
else:
smaller_permutations = permute(s[1:])
print("Inserting " + s[0] + " everywhere in ", smaller_permutations)
for x in smaller_permutations:
permutations = permutations + insert_char(s[0], x)
return (permutations)In the above function, permute, we pass the string to be permuted as an argument in variable “s”. The list “permutations” keeps a running tally of all permutations created and this is the returned value from this function. Now let us understand the logic. If ‘s” is either the empty string or a string containing only one character, then we simply return because there is either no permutation possible or only one permutation possible. These two base cases are covered in the first two clauses. If “s” has two or more characters, that is when the bulk of the work lies. We strip out the first character and call this function recursively with the shortened string (s[1:])). That will give us a list of permutations, which is stored in variable “smaller_permutations”. Then we put back the first character (that was taken out) back in every possible position in every string in smaller_permutations. This is done by invoking the insert_char() function inside a for loop. Finally, the permutations variable is returned. (We added a print statement for ease of understanding).
Here is the full program that is self-contained and calls it with a sample string (“kode”):
def insert_char(c, s):
insertions = []
insertions.append(c + s)
for (i, x) in enumerate(s):
t = s[0:i + 1] + c + s[i + 1:len(s)]
insertions.append(t)
return (insertions)
def permute(s):
permutations = []
if (len(s) == 0):
return(permutations)
elif (len(s) == 1):
permutations.append(s)
return (permutations)
else:
smaller_permutations = permute(s[1:])
print("Inserting " + s[0] + " everywhere in ", smaller_permutations)
for x in smaller_permutations:
permutations = permutations + insert_char(s[0], x)
return (permutations)
mystring = "kode"
variations = permute(mystring)
print(variations)
print("Total permutations = " + str(len(variations)))The output is:
Inserting d everywhere in ['e']
Inserting o everywhere in ['de', 'ed']
Inserting k everywhere in ['ode', 'doe', 'deo', 'oed', 'eod', 'edo']
['kode', 'okde', 'odke', 'odek', 'kdoe', 'dkoe', 'doke', 'doek',
'kdeo', 'dkeo', 'deko', 'deok', 'koed', 'oked', 'oekd', 'oedk',
'keod', 'ekod', 'eokd', 'eodk', 'kedo', 'ekdo', 'edko', 'edok']
Total permutations = 24As you can see the smallest recursion happens when we have only one character, i.e., for the last character of “kode”, which is “e”. Then “d” is inserted in every possible way into the “e” string, which yields: ['de', 'ed']. Then “o” is inserted everywhere in ['de', 'ed'] yielding ['ode', 'doe', 'deo', 'oed', 'eod', 'edo']. Finally, “k” is inserted everywhere, yielding our 24 desired permutations.
Try it with a longer string and explore how the program works!
Note that the program does not do anything special if you have repeated characters. You will have to post-process the permutations to remove duplicates. For instance, if we permute “odd” (just replace “mystring” in the above program), we will get:
['odd', 'dod', 'ddo', 'odd', 'dod', 'ddo']Thus even though it generates 6 permutations, there are really only 3 unique ones because the “d”s are interchangeablle.
Method 2: Use the itertools module to generate all permutations
The itertools module is a very handy way to generate all permutations:
from itertools import permutations
mystring = "odd"
variations = permutations(mystring)
print(variations)See how succinct the program is? This is because somebody else (the itertools module creator) has taken the trouble to develop a function called “permutations” that we can just invoke without worrying about how it works internally. The output is (something like):
<itertools.permutations object at 0x7fea30e409f0>This is not very descriptive. We need to unpack this object, like so:
from itertools import permutations
mystring = "odd"
variations = permutations(mystring)
for x in variations:
print(x)Now the output is:
('o', 'd', 'd')
('o', 'd', 'd')
('d', 'o', 'd')
('d', 'd', 'o')
('d', 'o', 'd')
('d', 'd', 'o')Note that it has separated out each of the strings into individual characters and not presented them as strings. To accomplish that we can use the join() function:
from itertools import permutations
mystring = "odd"
variations = permutations(mystring)
for x in variations:
print(''.join(x))This will yield what we are looking for:
odd
odd
dod
ddo
dod
ddoTo summarize, we have seen different ways to find all possible permutations of a given string in Python. The first is our own recursive implementation from first principles and the second is the permutations() function in the itertools module. No matter which one you use, the elegance with which you can use functional programming to compute all permutations makes this a very easy problem to solve in Python!
For more Python content, checkout the math.ceil() and math.floor() functions! Also
learn about the math domain error in Python and how to fix it!
Interested in more things Python? Checkout our post on Python queues. Also see our blogpost on Python's enumerate() capability. Also if you like Python+math content, see our blogpost on Magic Squares. Finally, master the Python print function!
Want to learn Python with us? Sign up for 1:1 or small group classes.
