This post is inspired by two questions. The first one was over lunch. A mate of mine explained that he had bought a new door lock and it was the type with 10 buttons. You can choose a code of 4, 5, or 6 digits. To open the lock, you punch in the digits. The order in which you punch in the digits does not matter. So, my friend asked, how long should the code be in order to maximise the number of combinations.

I thought that it should not take too long to write a Python program that would figure this out. So after lunch I typed in the following program:

import itertools

digits = '0123456789'

for key in range(1, len(digits)):
    print key, len([i for i in itertools.combinations(digits, key)])

Which gave the following output:

1 10
2 45
3 120
4 210
5 252
6 210
7 120
8 45
9 10
10 1

The program worked, ran in under a second, and gave the correct answer. In case you’re not clear how it works, it enumerates all the possible combinations and then counts up the number of values. This is fine when we have around 10 digits, but what if we had 26 digits (e.g. A-Z).

Well, the program now runs in about 10 or more seconds and we see that for a code length of 13 there are over 10,000,000 combinations.

This brings us to the second question. There was a question on Quora that asked “Does a person need mathematics to do computer science?”.

Well, suppose we now had 36 digits available to us (0-9 and A-Z), how long would we expect our program to take to run. At this stage, we stop thinking about a programming solution and start thinking about a mathematical solution.

I will cut through a lot of the maths and go back to the case where we have 10 digits. Suppose we are choosing a 4-digit code, there are 10 ways we can choose the first digit, once we’ve chosen it, there are 9 ways to choose the second digit, eight ways to choose the third, etc. In other words, to choose 4 digits, there are 10 x 9 x 8 x 7 ways we can do it. However, this covers all combinations such as 1234, 1324, 1423 etc. So, we divide this number by the number of ways we can choose 4 digits which turns out to be 1 x 2 x 3 x 4.

The following program implements this:

def factorial(n):
    """Return n!"""
    result = 1
    for i in range(n):
        result *= i+1
    return result

def combinations(n, k):
    """Return the number of combinations of k items selected from n choices"""
    return factorial(n)/factorial(n-k)


for i in range(10):
    print(i, combinations(10, i)/combinations(i,i))

This gives as the same output as the previous program, but without explicitly generating each combination.

We can now generate the results for our 36 digit lock and we get that 18 has the most combinations at 9,075,135,300 or around 9 billion different combinations. This would have taken hours to generate using our original program.

However, the original question was how many digits should we use to have the most combinations. A mathematical mind may look at the results and notice a symmetry around them. We get more combinations as we increase the number of digits and then at some point it starts decreasing. So, using a code of length 1 has the same number of combinations of a code of length n-1. However, for a mathematical mind, it is not enough to just notice the symmetry, we have to convince ourselves that it is correct. If we think about it for a moment, if we choose 1 digit (from a 10-digit lock), it is exactly the same as not choosing 9 digits, and choosing 9 digits is exactly the same as not choosing 1 digit.

So, here is a short Python program that prints the optimum length of code to choose:

digits = 10
print(int(digits / 2))

So, yes, in answer to the second question, I believe that maths is important in programming.