Permutations part two

1. Review

There are a bunch of small problems here — I think that if you had given yourself some more time (or looked more carefully at the answers you were given to your previous question) then you would have been able to fix many of them yourself.

1. Missing docstrings — you've written one for factors_factorial but what do the other functions do?

2. Vague variable names — what kind of object is obj? What kinds of objects are counted by obj_count? The name i is normally used for indexes but this code uses it for characters, so c would be better. I would expect the name p to refer to a prime, but here it refers to a count or multiplicity, so n or m would be better.

3. For portability to Python 3 it's a good plan to stick to // for integer division and / for floating-point division. In Python 2 you can use from __future__ import division to enforce the Python 3 semantics. (Note that PEP 238 is from 2001 — fifteen years later you shouldn't be writing new code using the old semantics.)

4. In the expression:

   Counter([i for i in Counter(obj).values() if i > 1])
   

   there's no need to create a list which you are going to throw away again immediately — you can pass a generator expression directly to the Counter constructor.

5. Instead of looping over the keys of a mapping and then having a separate lookup to find the value, use the items method to loop over the keys and values simultaneously.

6. Instead of adjusting the values of factors one at a time:

   count_p = factors_factorial(n, m)
   for prime in count_p:
       factors[prime] -= count_p[prime]
   

   make use of the subtraction operation on Counter objects:

   factors -= factors_factorial(n, m)
   

7. Each time factors_factorial is called, it has to generate the primes again. It would be better to generate them just once.

8. Instead of log(n)/log(p), write log(n, p) and save a function call. See the math.log documentation.

9. This loop requires two calls to log, and computes a power on every iteration:

   for k in range(1, int(1+log(n)/log(p))):
       mul += n // p**k
   

   It's better to write the loop like this:

   k = n
   while k:
       k //= p
       mul += k
   

   Writing it like this is not only simpler and avoids the power, but k gets smaller on each iteration, and so the divisions get cheaper as you go along.

2. Use NumPy

The code in the post imports NumPy in order to use numpy.prod. But if you're going to use NumPy at all, then there's no reason not to use it throughout the code:

import numpy as np

def factorial_factors_powers(primes, n):
    """Return an array containing the power of each prime in the
    factorization of n!.

    """
    p = primes
    n = np.full_like(p, n)
    result = r = np.zeros_like(p)
    while True:
        n //= p
        if n[-1] == 0:       # some primes not contributing any more?
            l = n.argmin()   # number of primes still contributing
            if l == 0:
                break
            n, r, p = n[:l], r[:l], p[:l]
        r += n
    return result

def fast_unique_perms(s):
    """Return the number of unique permutations of the string s."""
    s = str(s)
    primes = generate_primes(len(s) + 1)
    powers = factorial_factors_powers(primes, len(s))
    for n, m in Counter(Counter(s).values()).items():
        if n > 1:
            powers -= factorial_factors_powers(primes, n) * m
    return np.prod(np.array(primes, dtype=int) ** powers)

Note the use of dtype=int to force NumPy to do the final set of multiplications using Python's bignums instead of NumPy's fixed-width numbers.

This is around five times as fast as the code in the post.