Permutation in JavaScript

Permutation problems seek to generate all possible outcomes of a given input. For example, given three numbers how many possible different strings of those numbers could you create (123, 321, 213 etc)? Generally there are two classes of permutation problems, ones with repetition and ones without. Repetition allows options to be reused (so 111, 122, 123, etc) while no repetition means that each option can only be used once. In this post, we will walk through both cases with an ice cream shop example.

Ice Cream Permutation

Let’s say we are at an ice cream shop and are trying to decide what three scoops we want to get. We are wondering how many different options we can get, and what those options are. We are at the front of the line stuck looking at all the great flavors.

Pistachio ice cream…

To make it easy, lets say we are at a small ice cream shop that only has three flavors (pistachio, strawberry, and vanilla). How many different combinations are there?

The Math of Permutation with Repetition

Before we write out some formulas, lets just think about a couple of the options. I find in permutation (and in algorithms) it can be helpful to just write out a few examples to start seeing the pattern emerge. In our ice cream case, we could get a cone with three scoops of pistachio, two scoops of pistachio and one scoop of strawberry, two scoops of pistachio and one scoop of vanilla, and so on. As we continue to write out some of the options, we start to see our pattern arising. The total number of options is equal to the number of ice cream flavors multiped x times with x being the number of scoops we will get. In other words:

total number of options = ice cream flavors x ice cream flavors x ice cream flavors

which is the same as saying,

total number of options = (number of ice cream flavors)^(number of scoops)
total number of permutations = (number of choices)^(number of times we will choose)

For our ice cream case, it happens to be 3³ but say we added in another ice cream flavor (chocolate), then we would have 4³ total number of options. Now we know how many options we can have, let’s look in to how we would program to generate these options.

Programming Permutation with Repetition

Take a moment to try to program out a solution (or at least pseudocode one). You’ll learn much more from attempting on your own before reading a solution. Okay, after having done that let’s look in to our program. What does this problem look like?

The key to solving permutation problems is understanding the structure of your choices. Looking at our ice cream shop, we can think of it as a tree-like data structure and as I talked about in my recursion post, we can tackle a tree-like data structure with recursion. We can think of each step down the tree as choosing our flavor and the nodes as being each flavor. So our tree here would have four nodes underneath with each flavor being one of the nodes, and they would each have four nodes with each flavor, and so on until we hit our three scoops. How could we program this out?

Look back over the recursion post and think of emulating one of those methods and then come back and check the code below.

function iceCreamDecisions (totalScoops) {
  // Create an options array with all of the potential flavors
  var flavors = ["pistachio", "strawberry", "vanilla", "chocolate"];
  // Create a storage array of our choices
  var options = [];
 
  // Create our recursive function
  var iceCreamScoopChoice = function(scoopsLeft, scoopChoices) {
    // Base case, once we have chosen the full number of scoops
    if (scoopsLeft === 0) {
      options.push(scoopChoices);
      return;
    }
 
    // Otherwise, call our recursive function
    for (var i=0; i<flavors.length; i++) {
      iceCreamScoopChoice(scoopsLeft-1, scoopChoices.concat(flavors[i] + " "));
    }
  };
 
  // Call our recursive function
  iceCreamScoopChoice(totalScoops, ''); 
  // Return all of our options
  return options;
}

See how similar this problem is to our basic recursion solution? If we can correctly identify the structure of a problem, we will have a much easier time arriving at a possible solution. With permutation and any algorithm based problems, take time at the beginning to really understand your expected inputs and what you want your outputs to be. Think through what it would take to get from the inputs to the outputs. Then start pseudocoding, consider if that will truly get you there and then begin coding. Far too often people jump in to coding before really seeing the problem as a whole.

Permutation with Combination

Lets say we do not want to consider cases where we repeat our flavor choices. We can again think of this as a tree-like structure, but there is one major difference. The nodes below will only be the other remaining flavors. So as we take a step down the tree, our options are limited to fewer flavors. Otherwise we can consider the problem nearly the same. The resulting number of options, will be different though.

The Math of Permutation without Repetition

As we make a choice, the number of our options is decreased by one and this continues as we make more and more choices. So the total number of our choices will have to factor in this decrease in values. To calculate the total number we need to use factorials (for example 4! = 4 * 3 * 2 * 1). We can see looking at the factorial that the numbers are getting less and less (like one flavor is being removed). With including the number of scoops we see that the total number of options can be thought of as such:

total number of options = (factorial of number of ice cream flavors) / (the factorial of (number of ice cream flavors - number of scoops)
total number of options = ((total number of choices)!)/((total number of choices - number of times we will choose)!)

Programming Permutation without Repetition

Look at the programming for permutation with repetition and think if there is a very simple way to factor in this limitation. After trying a few options come back and let’s look at one possible solution.

function iceCreamDecisions (totalScoops) {
  // Create an options array with all of the potential flavors
  var flavors = ["pistachio", "strawberry", "vanilla", "chocolate"];
  // Create a storage array of our choices
  var options = [];
 
  // Create our recursive function
  var iceCreamScoopChoice = function(scoopsLeft, scoopChoices, flavorsLeft) {
    // Base case, once we have chosen the full number of scoops
    if (scoopsLeft === 0) {
      options.push(scoopChoices);
      return;
    }
    // Otherwise, call our recursive function
    for (var i=0; i<flavorsLeft.length; i++) {
      // Create a copy of our flavors so we can remove an option with each recursive call
      var temp = flavorsLeft.slice();
      temp.splice(i,1);
      iceCreamScoopChoice(scoopsLeft-1, scoopChoices.concat(flavorsLeft[i] + " "), temp);
    }
  };
 
  // Call our recursive function
  iceCreamScoopChoice(totalScoops, '', flavors);
 
  // Return all of our options
  return options;
}

You can note that the code is almost the same, except for the fact that as we recursively call our function we are giving it a new flavors array that is getting smaller as we remove flavors from it. Other than that, the function works the same as permutation with repetition. Pretty cool right?

Permutation Conclusion

Permutation problems are a great example of utilizing recursion and can be fun algorithms to develop. There are many problems that can be thought of as permutations that you might not expect. For example, consider trying to place as many queens as you can on a chess board. You could approach that problem as a permutation. In that case, the steps we would be making would be different, but conceptually it is a permutation problem.

The key to permutation is identifying the problem as a permutation problem and understanding the structure of the inputs. Once you have established all of that, you merely will have to implement the recursive solution. So now get out there and try to solve your own permutation problem!