Summing all numbers that can be formed from a list of integers

Following a challenge on HackerRank, I want to find the sum of all numbers that have no more than x 4's, y 5's, and z 6's module 10^9 + 7. I'd like to know how I could improve this code below both for style and performance. Also, what's the canonical way to get unique permutations of a list that can include repeated elements?

import itertools
import sys
import collections

#create initial list based on input
x, y, z = map(int, sys.stdin.readline().split(' '))
permute_list = [4]*x + [5]*y + [6]*z

# collect iterators to permutations of all possible lengths
permuted = []
for i in range(1,(x+y+z+1)):
    permuted.append(itertools.permutations(permute_list, i))

# collect unique permutations from iterators
# there will be many repeats, anyway to avoid this inefficiency?
dynamic_table = collections.defaultdict(lambda: 0)
mod_var = (10**9 + 7)
for it in permuted:
    for i in it:
        new_sum = ''.join(map(str, i))
        if not dynamic_table[new_sum]:
            dynamic_table[new_sum] = int(new_sum)

print(sum(dynamic_table.values()) % mod_var)

I tried a few ways of doing this. What most surprised me is that implementing with a dictionary, as above, seems to beat a set implementation by about 30%, time-wise. Why is this? Also, what are some better ways to implement this and/or tweaks to the above code?

Imagine you had to do the same with 4 distinct digits, a, b, c and d, and lets forget for now about numbers with less than 4 digits. There are 4! arrangements of these 4 digits, of which 3! each will have the a in the first, second, third and fourth positions. So the contribution of the digit a to the overall sum will be a 3! 1111, and the total sum of all numbers generated from these four digits ends up being (a + b + c + d) 3! 1111. It is easy to check that this works comparing to a brute-force solution:

from itertools import  permutations

def sum_them_quick(a, b, c, d):
    return (a + b + c + d) * 3 * 2 * 1 * 1111

def sum_them_slow(a, b, c, d):
    total = 0
    for digits in permutations([a, b, c, d], 4):
        total += int(''.join(str(d) for d in digits))
    return total

If you test this, you will find that, while they both produce the same result, the performance is already 100x faster for this small example:

>>> sum_them_quick(4, 5, 6, 7) ==  sum_them_slow(4, 5, 6, 7)
True
>>> %timeit sum_them_quick(4, 5, 6, 7)
1000000 loops, best of 3: 349 ns per loop
>>> %timeit sum_them_slow(4, 5, 6, 7)
10000 loops, best of 3: 54.9 µs per loop

Your case is not that simple, because you have to handle the repeats, but it isn't that much harder either. If you have x 4's, y 5's and z 6's, there are (x + y + z)! / x! / y! / z! different arrangements of those digits to form unique numbers. And similarly to the previous case, a 4 will show up in any given position x / (x + y + z) of the times. So similarly, the following function will compute the total sum in constant time:

from math import factorial    

def sum_them_456(x, y, z):
    total = 0
    for j in range(x + y + z):
        total *= 10
        total += 1
    print(total)
    total *= 4*x + 5*y + 6*z
    total *= factorial(x + y + z - 1)
    total //= factorial(x) * factorial(y) * factorial(z)
    return total

There are cleverer ways of computing a quotient of factorials, but that is left as exercise.

You also have to handle all the possible permutations with less than the full x + y + z possible digits. There may be a better way of not having to brute-force your way through this, but I'm out of cleverness right now, so I am going to go with something very unsophisticated:

def sum_them_all_456(x, y, z):
    n = x + y + z
    total = 0
    trials = set()
    trials.add((x, y, z))
    while n > 0:
        new_trials = set()
        for trial in trials:
            total += sum_them_456(*trial)
            for idx in range(len(trial)):
                if trial[idx] > 0:
                    new_trial = trial[:idx] + (trial[idx] - 1,) + trial[idx+1:]
                    new_trials.add(new_trial)
        trials = new_trials
        n -= 1
    return total

It still manages to handle values of x, y or z in the tenths in the blink of an eye, but there has to be a better way for this.

StackExchange Code Review Q#97254, answer score: 5