Counting permutations without repetitions for a number or a string

Can I make the following code faster with minor modifications? It times out on CodeWars website.

'''
Write a function that takes a number or a string and gives back the number of
permutations without repetitions that can generated using all its element
'''

from itertools import permutations
def perms(object):
    string = str(object)
    perm_set = []
    perm_repeated = permutations(string)
    print(perm_repeated)

    perm_list = [''.join(p) for p in permutations(string)]
    for item in perm_list:
        if item not in perm_set:
            perm_set.append(item)
    return len(perm_set)

#print(perms(737)) == 3

One of the best ways to make a program faster is not to compute things that you don't have to. In this question you are asked to compute the number of permutations. But your implementation goes and constructs all the permutations themselves, only to throw them all away again. It would be better to count them directly, via some kind of a mathematical formula.

Let's take a simpler example to show how this might work. Supposing that you knew that the string you are given has no repeated characters, for example ABC. Then the permutations are:

ABC ACB BAC BCA CAB CBA


but we can count them by observing that there are 3 choices for the first letter, 2 for the second, and one for the third, hence the total number of permutations is \$3 × 2 × 1 = 6\$. We call this "3 factorial" and write \$3! = 6\$.

In the actual question, the string might have repetitions. So let's look at a simple example. Suppose we are given the string AABC, with a repeated letter. Let's distinguish the two copies of A (for the moment) by writing one of them as a and generate all \$4! = 4 × 3 × 2 × 1 = 24\$ permutations:

AaBC AaCB ABaC ABCa ACaB ACBa BAaC BACa BCAa CAaB CABa CBAa
aABC aACB aBAC aBCA aCAB aCBA BaAC BaCA BCaA CaAB CaBA CBaA


You'll see that these permutation come in twos: one with A before a (I've put these in the top row) and the other with a before A (in the bottom row). Two is of course the number of permutations of two items: \$2! = 2\$. So if we go back to the situation where A and a are indistinguishable, there are \${4! \over 2!} = {24 \over 2} = 12\$ permutations.

One more example. Suppose the string is AAAB, with one letter repeated three times. Let's distinguish the three copies as before, and generate all \$4 × 3 × 2 × 1 = 24\$ permutations:

AaαB AaBα ABaα BAaα
AαaB AαBa ABαa BAαa
aAαB aABα aBAα BaAα
aαAB aαBA aBαA BaαA
αAaB αABa αBAa BαAa
αaAB αaBA αBaA BαaA


You'll see that these permutations come in columns of six: in each column there's one with A before a before α, one with A before α before a, and so on, for each of the \$3! = 6\$ permutations of Aaα. So if we go back to the situation where all the As are indistinguishable, there are \${4! \over 3!} = {24 \over 6} = 4\$ permutations.

In the general case where you have a string of \$n\$ letters where \$n_1\$ of them are identical, and another \$n_2\$ of them are also identical, and so on, then the number of permutations is the multinomial formula $$ {n! \over n_1!\,n_2!\ldots n_k!}. $$

So that's easy to program, using collections.Counter to count the number of occurrences of each character in the string, and math.factorial to compute the factorials:

from collections import Counter
from math import factorial

def permutation_count(s):
    """Return the number of different permutations of s."""
    s = str(s)
    c = 1
    for i in Counter(s).values():
        c *= factorial(i)
    return factorial(len(s)) // c

And since it doesn't have to construct all the permutations, it can count large numbers of permutations in a fraction of a second:

>>> permutation_count('AAAABBBCCDDEEFFGHIJKLMNOPQRSTUVWXYZ')
4484873249299542070167817420800000000

A quick timing comparison. First, your code from the post:

>>> from timeit import timeit
>>> timeit(lambda:perms('AAABBCDEF'), number=1)
201.83495365083218

Second, the revised code using a set:

>>> timeit(lambda:len(set(permutations('AAABBCDEF'))), number=1)
0.09620095230638981

Third, counting them directly:

>>> timeit(lambda:permutation_count('AAABBCDEF'), number=1)
5.3646042943000793e-05

That's about 54 microseconds, about 3.7 million times faster than the code in the post.

StackExchange Code Review Q#132704, answer score: 40