Recursive function for generating all permutations of an input string — InterviewCake

The problem is borrowed from InterviewCake. Although they did a great job explaining the solution in detail, there aren’t that many visuals.

This post is my attempt to visualize the solution:

Sample I/O

Input: ‘cat’

output: {‘cat’, ‘atc’, ‘act’, ‘tca’, ‘tac’, ‘cta’}

The Pattern:

Let’s start small. With 2 chars only.

Suppose we had ca as input.

Their permutations will be:

ca, ac

Notice that if we separated out the last char a and only had c then we are basically attaching the last char (a) into 2 different positions:

Next, let’s add another char.

Suppose we had cat as input:

Similar as above we separate out the last char t , Now notice we could place t in three different positions:

• cat
• tca
• cta

but then again we also can permute ca

Wait! we just did that in the previous step, when we generated ca and ac

So, we can add the last char: t in three positions of ca and ac

We would get

ca:

• cat
• tca
• cta

ac:

• act
• tac
• atc

Bam! we have all of our permutations!!

Visuals

computing all permutations of ‘CAT’

Implementation (Python3)

stack frames in the recursive call

It took me quite somet time to wrap my head around reading the descriptive solution on InterviewCake without any visuals. But with proper visuals, it’s easy peasy!

Key Takeaways:

• Breakdown the problem into its simplest part then solve that. Replicate that for bigger input
• Remember in recursive calls: the stack frames of a function saves that particular state of the function. You can use these stuffs!
• Always draw the recursive calls! Helps understand the different states