### Dennis Hackethal’s Blog

My blog about philosophy, coding, and anything else that interests me.

# 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 223, which is equal to 810 (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 (32).

## 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++) {
}
``````

This code counts from zero up to the greatest number in base 3 (again, that’s 223 or 810) 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'];

// 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 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.

Markdown supported. `cmd + enter` to comment. Your comment will appear upon approval. You are responsible for what you write. Terms, privacy policy