Using combinatorics in Python to list 4-digit passcodes

combinatorics, list, passwords, permutation, python

Solution

There is no `combinatorics` module in the standard distribution, but this is easy to do regardless. For example,

def guess(smudged_numbers):
    from itertools import product
    num_smudges = len(smudged_numbers)
    for raw in product(smudged_numbers, repeat=4):
        if len(set(raw)) == num_smudges:
            yield raw

count = 0
for nums in guess([1, 8]):
    print nums
    count += 1
print "total", count

That prints:

(1, 1, 1, 8)
(1, 1, 8, 1)
(1, 1, 8, 8)
(1, 8, 1, 1)
(1, 8, 1, 8)
(1, 8, 8, 1)
(1, 8, 8, 8)
(8, 1, 1, 1)
(8, 1, 1, 8)
(8, 1, 8, 1)
(8, 1, 8, 8)
(8, 8, 1, 1)
(8, 8, 1, 8)
(8, 8, 8, 1)
total 14

The search space is very small (`len(num_smudges)**4`, which as at most 4**4 = 256), so no point to doing anything fancier ;-)

How it works: it generates all possible (`product`) 4-tuples (`repeat=4`) containing the passed-in sequence of smudged numbers. So for `[1, 8]`, it generates all 2**4 = `len(smudged_numbers)**4` = 16 possibilities for a 4-tuple containing nothing but 1's and 8's.

Converting a raw possibility to a `set` then tells us how many (`len`) different numbers appear in the raw 4-tuple. We only want those containing all the smudged numbers. That's all there is to it. In the `[1, 8]` case, this step only weeds out 2 of the 16 raw 4-tuples: `(1, 1, 1, 1)` and `(8, 8, 8, 8)`.

Problem

I came across this interesting article about why using 3 unique numbers for a 4-digit passcode is the most secure: (LINK) The math involved is pretty straightforward - if you have to guess a phone's 4-digit passcode based on the smudges left on the screen, then: 4 smudges indicates that there are 4 unique numbers in the passcode. Since each of them must be used at least once, then we have `4! = 24` possible passcodes. With 3 distinct numbers, the passcode becomes a little more secure. Since there are three smudges, one number is repeated - but we don't know which one. So accounting for multiplicity, we get `(4!/2!) x 3 = 36` possible passcodes. Similarly, with 2 distinct numbers, we get 14 possible passcodes. My question is, is there any way I can "prove" the above in Python? A way to justify that 3 numbers gives the most secure passcode, with Python code, probably something that lists out all possible passcodes if you give it some numbers? I was thinking about using `itertools`, with `itertools.permutations` as a starting point, but then I found that Python has a combinatorics module, which may be a far more elegant way. Would someone be kind enough to show me how to use it? I'm reading the documentation right now but some syntax is escaping me.

Original source