Algorithm practice: find all possible permutations of an input string (without using .permutation)

Julia Herron
Jan 18, 2016 · 3 min read

This problem will probably seem very simple and straight-forward for Ruby veterans, but I’d like to break it down for people new to Ruby or recursion.

Here’s the prompt:

Find all possible permutations of an input string. For example, the input “ABC” would return the following: “ABC”, “ACB”, “BAC”, “BCA”, “CBA”, and “CAB”. Do NOT use the built-in “.permutation” function.

I thought about a couple approaches here. What if I initialized an empty array, split the string into an array of letters, ran “shuffle” on the array, stitched it back together, and added it to my results array if it wasn’t already in there? This is the dirty, brute-force attempt. I didn’t like that I was switching types unnecessarily, and I would almost guarantee that my code was running more than necessary (because shuffle is pseudo-random, which is a whole other conversation). My next approach was to do the shuffling in a programmatic way — manually change the order of my letters, and then run my function recursively to get each variation.

Here’s what I came up with:

# rubydef permutations(array, index=0)
p array if index == array.size
(index..array.size-1).each do |swap|
array[index], array[swap] = array[swap], array[index]
permutations(array, index+1)
array[index], array[swap] = array[swap], array[index]
end
end

For our example “ABC”, stepping through the code line by line gives us the following:

# print array if 0 == 3 ← false
# from 0 to (3–1), so from 0 to 2, do the following:
# i is 0, and j is also 0
# swap A with A
# run “permutations” function on (“ABC”, 1)
# print array if 1 == 3
# swap array[1] with array[0], so B for A
# run “permutations” on (“BAC”, 2)
# print array if 2 == 3
# swap array[2] and array[0], so C for B
# run “permutations” on (“CAB”, 3)
# print array because 3 == 3, so “CAB”
# switch A back with A
# go back through each stack and print the permutations

This becomes more obvious when we add some print statements throughout the function (feel free to run this yourself in IRB):

# rubydef permutations(array, i=0)
puts “this is i at the beginning: #{i}, this is the array size: # {array.size}”
p array if i == array.size
(i..array.size-1).each do |j|
array[i], array[j] = array[j], array[i]
puts “this is the array after the swap: #{array}”
permutations(array, i+1)
puts “exited recursive calls”
array[i], array[j] = array[j], array[i]
puts “array after the second swap: #{array}”
end
end

To check the answer, I started thinking about how many permutations we should get from a string of length n. The formula for “no repetition, order matters” is: (n! / (n — r)!), where n is the number of things to choose from (3), and r is how many items we choose (3). So that gives us (3 x 2 x 1) / (0!), which is 6. And we do indeed get 6 strings back. Taking a look at the string “ABCDE”, we get 5! variations, or 120.

I’m curious to see how other people solved this problem. Specifically, I’m wondering if an iterative version improves readability. Also - has anyone gotten this problem during an actual interview? Let me know!

Julia Herron

Written by

Web developer | Github: https://github.com/cadyherron | Twitter: https://twitter.com/juliaherron | www.juliahf.com