Fun Toy Problem !

Li Shao
Li Shao
Jun 19, 2017 · 2 min read

The other day someone told me that permutations has been a growing to be quite the popular technical interview question these days. Since I have been a math professor who has repeatedly taught statistics courses, I have been become very familiar with the topic of permutations. For example, a common permutation scenario in statistics would be:

Consider a committee that consists of 5 people. One person is to be chosen to be president, one the vice president, and another person to be secretary. How many ways can this be achieved with the 5 people currently in the committee?

Since permutations have been a part of my curriculum in mathematics and now, engineering, this is why I decided to talk about permutations this week.

Prompt: Write a function that takes in a string and we must generate a function that finds all anagrams of that string. We will assume that anagrams include permutations of letters that may not generate a resulting dictionary word.

Example: Let’s consider our given string is ‘ant’. Then the function should spit out the following collection:

[‘atn’, ‘tan’, ‘tna’, ‘nat’, ‘nta’]

When I was white boarding this problem, I noticed this question may be tackled with an idea of using a decision tree. I will only mention one possible decision tree, but note that this process is repeated for all letters in the given string. Say the first element I take from the given string is ‘t’. Then when I take the ‘t’, it’s obvious to see that there are now two possibilities of what can come after that, namely, ‘a’ or ‘n’. Once the next letter is chosen to go after the ‘t’, then there’s only one possible letter left to fill the last spot of the permutation (Say, ‘tan’ and ‘tna’). A pic for your convenience:

Furthermore, as a result of the decision tree making progress and it’s repetitiveness, this then led me to think along the lines of using recursion (ie: making the decision trees seem to be a process that is repeated in the same fashion).

The explanation behind the upcoming code:

The input has the form of a string. I will develop permutations by first transforming the string into an array of it’s letters as elements. I will then develop an inner recursive function that will iterate through the array of letters and repeatedly track each branch of a decision tree. Then spit out the all permutations of the given string as a collection in an array.

Li Shao

Written by

Li Shao

A math professor turned UX Developer at Indeed.com

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade