Password Attacker (Google apac test problem)
This kind of problem can be solved with dynamic programming. The key points are :


you care about the number of combinations and not the list of them
assuming you know how to compute it for some values, you can go forward and compute it for even more values.


Here is how it could go (not verified whatsoever).

Given the length n (n > 0) and the number of distinct characters m (m > 0), you know that :


nb_comb(n, 1) = 1 which corresponds to strings with a single character.
nb_comb(n, m) = 0 if 1 &lt;= n &lt; m which corresponds to the fact that the string is too short to use all characters
nb_comb(n, m) = m * nb_comb(n-1, m-1) + m * nb_comb(n-1, m) if 1 &lt; m &lt; n which corresponds to the fact that to build a string of n characters, you can consider that you have to build a string of length n-1 and to add one at the end. Basically, you can either :


consider strings containing m-1 distinct characters and add the missing character : you have nb_comb(n-1, m-1) such strings for each of the m distinct characters. This contributes to m * nb_comb(n-1, m-1) combinations.
consider string containing all m characters and add any of the already added character : you have nb_comb(n-1, m) such strings and m ways to add an already existing character at the end. This contributes to m * nb_comb(n-1, m) new combinations.



(You can check that strings have not been counted twice (either the last character is a duplicate from another or it is not a duplicate).)

Without knowing it corresponds to Stirling numbers, I managed to deduce the same equations as the one in that stackoverflow question.



Python recursive solution to check it works :

import itertools

def nb(n, m):
    #print(n, m, "?")
    assert n&gt;0
    assert m&gt;0
    if m == 1:
        res = 1
    elif n == 1:
        res = 0
    else:
        res = m * (nb(n-1, m-1) + nb(n-1, m))
    if False: # check results
        slow_res = sum(1 for p in itertools.product(range(m), repeat=n) if len(set(p)) == m)
        assert slow_res == res
    return res

tests = [
    (1, 1, 1),
    (2, 2, 2),
    (3, 3, 6),
    (4, 3, 36),
    (5, 5, 120),
    (15, 15, 674358851),
]
for n, m, r in tests:
    nb_ = nb(n, m) % (1000000007)
    assert nb_ == r, "(%s,%s,%s != %s)" % (n, m, r, nb_)




This still gets way too slow for bigger solutions. Having a look at the functions calls for the case 15-15, for instance, adding a call to print at the beginning of the fonction and running python my_script | sort -n | uniq -c | sort -n, you get :

   ...
   1001 (1, 11)
   1001 (1, 5)
   1287 (2, 10)
   1287 (2, 7)
   1716 (2, 8)
   1716 (2, 9)
   2002 (1, 10)
   2002 (1, 6)
   3003 (1, 7)
   3003 (1, 9)
   3432 (1, 8)


showing that the fonction gets called with the same arguments thousands of times.

A solution would be memoization but a better one is to go the other way, generating the different values.

A way to do so is :

def nb2(n, m):
    # nb(i, j) is in results[i-1][j-1]
    results = [[None for j in range(m)] for i in range(n)]
    for j in range(m):
        results[0][j] = 0
    for i in range(n):
        results[i][0] = 1
    for i in range(1, n):
        for j in range(1, m):
            results[i][j] = (j+1) * (results[i-1][j-1] + results[i-1][j])
    return results[n-1][m-1]