In my quest to learn the intricacies of Python, I came across one of my favorite algorithms; finding all the possible permutations of a string.
To lay it out:
# Given string 'ab'
# Permutation list ['a', 'ab', 'b', 'ba']
This is a poster child for recursion. To set it up, we'll have our primary function, string_permutations, but also define a subroutine that will do our recursive dirt work. We'll also create a combos list to hold onto our permutations.
#!/usr/bin/env python -tt
def string_permutations(string):
def sub_routine(...some args):
combos = []
return combos
return sub_routine(...some args)
def main():
# print string_permutations('ab')
if __name__ == "__main__":
main()
We'll pass in two list arguments to sub_routine. The first will hold on to all the characters that we have 'used' so far, and the other will hold on to the characters that we still have left to use. We can call sub_routine in our parent function beginning with an empty list for 'used' characters, and a list made of all characters in the target string as the initial 'left' characters.
...
def sub_routine(used, left):
combos = []
return combos
return sub_routine([], list(string))
Inside our sub_routine function, we can begin generating our permutations. First, we'll loop through each index in the left list. Looping the index and not the character itself, will make it easier to manage the recursion later on. Then, we'll remove the character from the left list at that index and add it to the end of the used list.
The used list will represent our permutation so far. We're not implementing restrictions on the size of the permutations, so each iteration will represent a unique permutation. We can then push that permutation to our combos list.
...
def sub_routine(used, left):
combos = []
for i in range(0, len(left)):
ch = left.pop(i)
used.append(ch)
combos.append(''.join(used))
return combos
return sub_routine([], list(string))
And now, here comes the fun part. For each permutation we start building, we need to add on all combinations of remaining characters. So let's get a little recursive.
What we'll do is pass in the new used and left lists to a recursive call to our sub_routine. Since our sub_routine will return all of its subsequent permutations, we can concatenate the result of our recursive call with our combos array.
The tricky part comes in after we make the recursive call. We have to reset the contents of left and used so that when we continue on in the for loop, we can access the next character properly.
For example, on the first iteration of 'ab':
# First iteration:
# ch will equal 'a'
# We will put 'a' into our used array as the first character.
# All subsequent recursive calls down this path will have 'a' as the first character.
# We finish the recursive chain, and replace 'a' in left and remove 'a' from used.
#Second Iteration:
# ch will equal 'b'
# We will put 'b' into our used array as the first character.
# All subsequent recursive calls down this path will have 'b' as the first character.
All of these steps will be repeated as part of the recursion with the result that each permutation will be visited.
#!/usr/bin/env python -tt
def string_permutations(string):
def sub_routine(used, left):
combos = []
for i in range(0, len(left)):
ch = left.pop(i)
used.append(ch)
combos.append(''.join(used))
# Append the results of the
# recursive call to our combos list
combos = combos + sub_routine(used, left)
# Remove ch from used
used.pop(-1)
# Splice ch back into left at its original index
left[i:0] = [ch]
return combos
return sub_routine([], list(string))
def main():
print string_permutations('ab')
if __name__ == "__main__":
main()
Knocking out a permutations algorithm always makes me feel like a recursive badass.