Password Attacker (Google apac test problem) Original Problem

Short Summary:




  Given a \$M\$ possible characters all of which must be used at least
  once, find the number of possible combinations of length (exactly)
  \$N\$. 
  
  The first input contains the number of cases, followed by pairs of M,
  N. Output is modulo 1000000007(\$10^9+7\$). 
  
  Example Input: 

4
1 1
3 4
5 5
15 15

  
  Example Output: 

Case #1: 1
Case #2: 36
Case #3: 120
Case #4: 674358851



The stupid solution is to simply generate all possible repeated_permutations and then exclude the ones which do not use at least M different characters (this of course is painfully slow).



def num_pw_slow(m,n)
  m.times.to_a.repeated_permutation(n).count do |row|
    m.times.map {|i| row.include? i}.all? 
  end
end


The real solution: 

It's noticeable that the number of solutions which include all M characters is also: (The number of repeated permutations) \$ - \$ (the number of repeated permutations missing at least one character). 

The number of repeated permutations is simply \$m^n\$. The second is a little more involved. Combinations are given by \$n!/ (n-k)!k!\$ where \$n=m\$ and \$k = m-1\$. Permutations are \$(m-1)^n\$, the tricky part is we need the set of permutations, since each of the \$(m-1)\$ possible combinations differs from another by a single character, its repeated_permutations will contain a duplicates for all permutations which exclude that character.

For example if m=3, n=4, there are \$3^4\$ repeated_permutations possible - with repeated permutations of ab, bc, ca (possible combinations of m, with length m-1) missing one required character when expanded to length n, the set operation over which needs to eliminate duplicates from repeated_permutations of a, b, c So the solution is then: 

3**4 - (2**4*3 - 1**4*3) 


This can be generalized for any m, n e.g. 

m**n - (m-1)*num_combinations**n
#second term is the number of duplicates amongst repeated_permutations of (m-1)
+ (m-2)*num_combinations**n 
#third term is the number of duplicates in the second term
- (m-3)*num_combinations**n 
#fourth term is duplicates in the third term
+ (m-4)*num_combinations**n
#and so on 


Which gives the following code in Ruby: 

(m**n) - (1..m-1).reduce(0) { |sum, i| sum + (i % 2 == 0 ? -1 : 1)*combinations(m, m-i)*(m-i)**n }


Full Solution: 

def factorial(num)
  (1..(num.zero? ? 1 : num)).reduce(:*)
end

def combinations(n, k)
  factorial(n) / (factorial(n-k)*factorial(k))
end

def num_pw(m, n)
  (m**n) - (1..m-1).reduce(0) { |sum, i| sum + (i % 2 == 0 ? -1 : 1)*combinations(m, m-i)*(m-i)**n }
end

num_cases = gets.chomp.to_i
num_cases.times do |num|
  m, n = gets.chomp.split.map(&amp;:to_i)
  puts "Case ##{num+1}: #{num_pw(m, n) % (10**9+7)}"
end


This took me over three hours to figure out (well over the exam running time) and quite inconsistent with my times on other problems (which are usually close or slightly better than average) - so for whoever solved this in under 45 minutes or so, I'd be very much interested how. Math SE gives a concise solution with the use of Sterling's number (I'd never heard of it before and I'm not sure if this is expected knowledge or not?)
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]