Bike Locks, Permutations and Combinations

Someone was recently talking to me about brute forcing an old bike lock – the usual type with four, rotating, numbered barrels. This lead to looking up a bit more than I needed solve the problem. I am aware of the usual shortcuts for opening these locks, but the method described was brute forcing.

 

Permutations

A permutation is an arrangement of items in a particular order. The formula for the total number of permutations of ‘n’ items taken ‘r’ at a time is:

nPr = n! / (n – r)!

Where ‘n!’ is the factorial of ‘n’ (the product of all positive integers from ‘1’ to ‘n’), and ‘(n – r)!’ is the factorial of ‘(n – r)’.

For example, suppose you have three different books (A, B, C). In that case, the different ways you can arrange 2 of them on a shelf (i.e., permutations) are AB, BA, AC, CA, BC, and CB, making six permutations in total.

 

Combinations

Unlike a permutation, a combination does not consider the order of items. So, it is a selection of items where the order is unimportant. The formula for the total number of combinations of ‘n’ items taken ‘r’ at a time is:

nCr = n! / [(r!)(n – r)!]

Using the previous example about books, the different combinations you can select 2 (ignoring order) are AB, AC, and BC, making three combinations in total.

Remember, permutations are about “arrangements” (order matters), while combinations are about “selections” (order does not matter).

 

Repetition

Permutations and combinations also have variations where you consider replacement (also referred to as repetition) of items. ‘Replacement’ means that after selecting an item, it’s returned to the set before the following selection.

 

Permutations with Replacement

In permutations with replacement, after selecting an item, it’s replaced into the original set. So, the number of permutations of ‘n’ items taken ‘r’ at a time when repetition is allowed is:

n^r

Because, for each of the ‘r’ positions, you can choose any of the ‘n’ items.

For example, if you’re creating a 3-letter code from the 26 letters of the English alphabet, the number of such codes you can make (permutations with replacement) would be 26^3.

 

Combinations with Replacement

In combination with replacement, you selecting ‘r’ items from ‘n’ choices and can pick the same item multiple times. The formula for this is:

(n + r – 1)Cr = (n + r – 1)! / [(r!) (n – 1)!]

For example, suppose you want to choose three fruits from a selection of apples, oranges, and bananas, and you can select the same fruit more than once. In that case, you’d use this formula to calculate the number of combinations.

Remember, with replacement or repetition, the same item can be selected more than once, which is why the number of possible outcomes increases.

This is all very interesting, but to return to our four-combination bike lock. The solution is relatively simple. Although at first thought, it might appear the bike lock is an ordered sequence of four numbers. If you think about it, it’s four separate permutations with replacement.

Each of the barrels, numbered from 0 to 9, can be calculated using using ‘n^r’ to have ten permutations – we can think of it as replacement or repetition, with only one selection. This means we have four lots of ten items with one item selected.

10^4 = 10000

It could therefore take up to 10000 tries to brute force the bike lock.