Jared NielsenIf you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to generate combinations in JavaScript and Python.
This tutorial originally published at jarednielsen.com
Retrieval Practice
Retrieval practice is the surest way to solidify any new learning. Attempt to answer the following questions before proceeding:
What is recursion?
What is a factorial?
What is a combination?
What is Recursion?
In computer science, recursion occurs when a function calls itself within its declaration.
We use recursion to solve a large problem by breaking it down into smaller instances of the same problem. Recursion consists of two things:
a base case
a recursive case
We use the recursive case to break the problem down into smaller instances.
We use the base case to stop when there are no more problems to be solved.
What is a Factorial?
A factorial is the product of all positive integers less than or equal to n.
We write that as n!.
For example, 5!:
5 * 4 * 3 * 2 * 1 = 120
What is a Combination?
According to ye olde Wikipedia:
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter
Here's the formula for combinations:
n! / (n - k)! * k!
...where n is the length of the set of values, and k is the number of values in each combination of n.
Let's Get Meta!
Ask yourself the following questions and keep them back of mind as you proceed:
Why do I need to know this?
What problem(s) does the combinations algorithm solve?
If you could be a tree, what kind of tree would you be?
How to Code the Combinations Algorithm
Programming is problem solving. There are four steps we need to take to solve any programming problem:
Understand the problem
Make a plan
Execute the plan
Evaluate the plan
Understand the Problem
To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:
GIVEN a sequence of integers from 1 to `n`
WHEN I specify the size of each set of combinations, `k`
THEN I am returned all possible combinations of the values from 1 to `n` in sets of size `k` without repetition
That’s our general outline. We know our input conditions, an array, and our output requirements, an array of combinations, and our goal is to calculate the number of k combinations in n without repetition.
Let’s make a plan!
Make a Plan
Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:
Decomposition
Pattern recognition
Abstraction
Algorithm design
The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?
If the length of n is equal to 1, then the only combination is:
[1]
What about k?
If n is equal to 2, and k is equal to 1, then our combinations are:
[1], [2]
If n is equal to 2, and k is equal to 2, then our only combination is:
[1, 2]
If n is equal to 3, and k is equal to 2, it starts to get interesting. Our combinations are:
[1, 2], [1, 3], [2, 3]
Do you see a pattern emerging?
Let's do one more...
If n is equal to 4, and k is equal to 1, our combinations are:
[1], [2], [3], [4]
If n is equal to 4, and k is equal to 2, our combinations are:
[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
If n is equal to 4, and k is equal to 3, our combinations are:
[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]
For good measure, if n is equal to 4, and k is equal to 4:
[1, 2, 3, 4]
We can see that we will need to iterate to generate our combinations, and that those loops will need to be nested, but just how many loops do we need to nest?
It depends!
We won't be able to hard-code in the nested loops. In the examples above, the number of iterations required to calculate the combinations ranges from 1 to 4. And we're only working with small values.
What's the solution?
Recursion!
As we recalled above, recursion consists of two things:
base case
recursive case
What's our base case?
k == 1
If k is equal to 1, then we simply return n.
Let's pseudocode that:
FUNCTION combinations(n, k)
SET combos TO AN EMPTY ARRAY
IF k IS EQUAL TO 1
RETURN n
If we pass our combinations function an array, n, containing five ordinal values, it will return just that:
[1, 2, 3, 4, 5]
What's the next problem we can solve?
Combinations with a length of 2!
If n is equal to [1, 2, 3, 4, 5] and k is equal to 2, then our goal is to return an array with the following combinations:
[ [ 1, 2 ],
[ 1, 3 ],
[ 1, 4 ],
[ 1, 5 ],
[ 2, 3 ],
[ 2, 4 ],
[ 2, 5 ],
[ 3, 4 ],
[ 3, 5 ],
[ 4, 5 ] ]
Do we see a pattern?
There are four combinations beginning with 1...
...and three combinations beginning with 2...
...and two combinations beginning with 3...
...and only one combination beginning with 4.
What does this tell us?
With each iteration over n, we decrement the next iteration by 1. In the first iteration, we are creating all of the combinations that begin with 1. In the second iteration, we are creating all of the combinations that begin with 2, in the third iteration, 3's, and finally 4.
Regardless of k, we're going to need at least two iterations. The first iteration will set the initial value of the combinations. The second iteration will iterate over the remaining values to create the combinations.
Let's illustrate this...
In our first iteration over n, we set the initial value of our combo arrays to 1.
[1]
Let's call this our head.
In a nested loop, we then iterate over the remaining elements in n, which are [2, 3, 4, 5]. Let's call this our tail. We concatenate each of the values in our head to create combo arrays.
[1, 2]
[1, 3]
[1, 4]
[1, 5]
We then return to the outer loop and move to the next value in n, which is 2. Our new head looks like this:
[2]
Again, we iterate over the remaining elements, or tail, concatenating each of these values to create combo arrays.
We decrement our iterations by slicing off the first element in n, and creating a new array, head.
Let's pseudocode this...
FUNCTION combinations(n, k)
SET combos TO AN EMPTY ARRAY
SET head
SET tail
IF k IS EQUAL TO 1
RETURN n
FOR EVERY VALUE i IN n
SET head EQUAL TO THE FIRST SLICE OF n
SET tail EQUAL TO THE REMAINDER OF n
FOR EVERY VALUE j IN tail
SET combo EQUAL TO head CONCATENATED WITH THE VALUE STORED IN tail[j]
PUSH combo TO combos
RETURN combos
What's the next smallest problem we can solve?
Combinations with a length of 3!
If n is equal to [1, 2, 3, 4, 5] and k is equal to 3, then our goal is to return an array with the following combinations:
[ [ 1, 2, 3 ],
[ 1, 2, 4 ],
[ 1, 2, 5 ],
[ 1, 3, 4 ],
[ 1, 3, 5 ],
[ 1, 4, 5 ],
[ 2, 3, 4 ],
[ 2, 3, 5 ],
[ 2, 4, 5 ],
[ 3, 4, 5 ] ]
Will the approach we outlined above work?
Nope. We could add another nested loop. But what do we do when k is equal to 4? Add another nested loop?
Do we need more loops?
Yes, but not the iterative variety.
We need to get abstract annd make the leap to recursion.
But where?
In the return statement?
If we recursively call combinations in the return, we would only use one nested loop.
We know we need at least one nested loop.
What if we called combinations within the first loop, but before the second loop?
This would allow us to use as many nested loops as necessary to create all of the combinations.
How are we catching the return value of combinations?
With every recursive call of combinations, we will create a new head from the next element in the array. We'll continue to make calls to combinations until the base case is met, where n is equal to 1.
What if we set the value of tail to the recursive calls of the combinations?
Let's pseudocode this...
FUNCTION combinations(n, k)
SET combos TO AN EMPTY ARRAY
SET head
SET tail
IF k IS EQUAL TO 1
RETURN n
FOR EVERY VALUE i IN n
SET head EQUAL TO THE FIRST SLICE OF n
SET tail EQUAL TO THE RETURN VALUE OF combinations(THE REMAINDER OF n, k - 1)
FOR EVERY VALUE j IN tail
SET combo EQUAL TO head CONCATENATED WITH THE VALUE STORED IN tail[j]
PUSH combo TO combos
RETURN combos
Execute the Plan
Now it's simply a matter of translating our pseudocode into the syntax of our programming language.
How to Code the Combinations Algorithm in JavaScript
Let's start with JavaScript...
const combinations = (n, k) => {
const combos = [];
let head, tail;
if (k === 1) {
return n;
}
for (let i = 0; i < n.length; i++) {
head = n.slice(i, i + 1);
tail = combinations(n.slice(i + 1), k - 1);
for (let j = 0; j < tail.length; j++) {
let combo = head.concat(tail[j]);
combos.push(combo);
}
}
return combos;
}
How to Code the Combinations Algorithm in Python
Now let's see it in Python...
def combinations(n, k):
combos = []
if (k == 1):
return n
for i in range(len(n)):
head = n[i:i+1]
tail = combinations(n[i+1:],k-1)
for j in range(len(tail)):
print("tail[j]", tail[j])
if (type(tail[j]) == int):
combo = head + [tail[j]]
else:
combo = head + tail[j]
combos.append(combo)
return combos
FYI, there's a combinations method built-in to Python. You need to import the itertools module to use it.
import itertools
It's use looks like this:
result = itertools.combinations(n, k)
Under the hood, it's implementation looks like this:
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
The more you know!
Evaluate the Plan
Can we do better?
Yes!
There are a few optimizations we can make to our algorithm. We can make the algorithm more efficient by only iterating over n.length - k + 1. In JavaScript, that would look like:
for (let i = 0; i < n.length - k + 1; i++) {
This reduces the number of iterations required to generate the combinations, but does not change the output of the algorithm.
We can make our algorithm more "idiomatic", or, at the very least, idiot proof, by refactoring our conditional to return combos rather than n. But this will require us to "manually" copy the values stored in n to combos, which is not necessarily efficient.
if (k === 1) {
for (let i = 0; i < n.length; i++) {
combos.push([n[i]]);
}
return combos;
}
We could also get ES6-y, and map the return.
return n.map(i => [i]);
We can also introduce more conditionals above the first to catch edge cases.
if (k > n.length || k < 1) {
return [];
}
if (k === n.length) {
return [ n ];
}
What is the Big O Of Combinations?
If you want to learn how to calculate time and space complexity, pick up your copy of The Little Book of Big O
Reflection
Remember those meta questions we asked at the outset? Let’s make it stick and answer them now!
Why do I need to know this?
What problem(s) does the combinations algorithm solve?
If you could be a tree, what kind of tree would you be?
Why Do I Need to Know This?
Understanding combinations will help you order better pizzas.
It will also help you identify when a problem might require a factorial solution, such as the knapsack problem, in which case you would want to use dynamic programming or a heuristic algorithm.
What Problem(s) Does the Combinations Algorithm Solve?
Other than generating combinations, it creates more problems than it solves with its time and space complexity!
If You Could Be a Tree, What Kind of Tree Would You Be?
I asked this at the outset to prime your thinking about trees. The combinations algorithm functions similarly to tree traversal.
A is for Algorithms
This tutorial is a chapter from my book. If you found it useful, grab your copy of A is for Algorithms
