The Easiest Way to Find All Permutations… Is Counting?!

When interviewing for a programming job, you may be asked: given two balls of up to three colors – say, red, blue, and green – which permutations can the set of all three have? In other words, find all possible permutations, from all red to all green and everything in between.

It occurred to me years ago (though I doubt that I’m the first) that all programming languages already have a built-in way to iterate through all possible permutations of sets: counting. Counting is itself based on iterating through all possible permutations of digits in some base up to a given number, in a specific order. Therefore, counting can be used to solve this problem.

To see how counting is a special case of permuting, consider the following list, generated by counting up in binary (ie, base 2). It would work the same for decimal (ie, base 10) but that would be a much longer list. Here are the numbers zero through three in binary; the first two are listed with a leading zero to make the permutations more apparent:

00
01
10
11

See how these are all possible permutations of two-digit numbers made of digits 0 and 1? And all we did was count!

More generally, when you count from 0 up to some number i in base n, you will have generated all possible permutations from 0 up to i for that base. Since we have three colors, we’d choose base 3, and since we have two balls, we’d count up to the greatest two-digit number in that base. The ‘trick’ is to consider each digit a different color – say, 0 is red, 1 is blue, and 2 is green – and then have the program count for you, thereby iterating through all possible permutations of these colors automatically.

In base 3 we have three digits: 0, 1, and 2. That means the greatest two-digit number in base 3 is written as 22₃, which is equal to 8₁₀ (read: the number ‘22’ in base 3 equals ‘8’ in base 10). By counting from 0 to 8 and adding leading zeros whenever there are less than 2 digits, we traverse a total of 9 numbers and determine each permutation along the way. And 9 is indeed the total number of permutations for a set of two elements with three possible values each (3²).

Implementation

Here’s how this approach looks in practice using JavaScript. To convert a number from base 3 into its decimal representation, you can use parseInt. For example:

parseInt('22', 3);
// => 8

To go the opposite way – from decimal to base 3 – we use toString:

(8).toString(3);
// => '22'

With that in mind, here’s how to determine all possible permutations for two balls of three potential colors:

for (let i = 0; i <= parseInt('22', 3); i++) {
  console.log(i.toString(3).padStart(2, '0'));
}

This code counts from zero up to the greatest number in base 3 (again, that’s 22₃ or 8₁₀) and adds a leading zero where necessary. It prints:

00
01
02
10
11
12
20
21
22

I said earlier that each digit corresponds to a color, so let’s reflect that:

for (let i = 0; i <= parseInt('22', 3); i++) {
  let colors = ['red', 'blue', 'green'];
  let digits = i.toString(3).padStart(2, '0');

  // Turn, say, '10' into 'blue, red'
  let convertedDigits = digits.split('').map(digit => colors[digit]).join(', ');

  console.log(convertedDigits);
}

Each element in the colors array corresponds to the digit equaling its own index. In other words, since ‘red’ is at index 0, it corresponds to digit 0, whereas ‘blue’, being at index 1, corresponds to digit 1, and so on. The colors can be looked up accordingly.

This code prints:

red, red
red, blue
red, green
blue, red
blue, blue
blue, green
green, red
green, blue
green, green

Here’s a generalization of this approach for any number of elements (ie, instead of just 2 balls it could be count of anything) with a given array of possible values (say, flavors instead of colors or whatever):

let permute = (count, values) => {
  let base = values.length;
  let max = (base - 1).toString().repeat(count);

  for (let i = 0; i <= parseInt(max, base); i++) {
    let digits = i.toString(base).padStart(max.length, '0');
    let convertedDigits = digits.split('').map(digit => values[digit]).join(', ');

    console.log(convertedDigits);
  }
};

For example, if the owner of a restaurant wants to know what combinations of three sweet and/or savory pancakes exist, he could run:

permute(3, ['sweet', 'savory']);

Which prints:

sweet, sweet, sweet
sweet, sweet, savory
sweet, savory, sweet
sweet, savory, savory
savory, sweet, sweet
savory, sweet, savory
savory, savory, sweet
savory, savory, savory

Bonus

There are some edge cases to consider. See if you can extend the permute function accordingly, if necessary. One is that the collection of possible values could be empty, in which case the function should return undefined. Or count could be 0, or negative, both of which should lead to the same result. Another edge case is that values only has one element, in which case max is 0 and no iteration occurs, ie nothing is ever logged; a line containing that single value m times should be logged instead. Lastly, values may contain duplicates; at the very beginning of the function, you could turn values into a set to remove duplicates and then back into an array.