12
\$\begingroup\$

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
\$\endgroup\$
37
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How does that perform if we end up getting really long strings? Does the factorial blow up, or at least does it blow up more slowly than the len(set(permutations)) method? \$\endgroup\$ – Dannnno Jun 22 '16 at 12:11
  • 2
    \$\begingroup\$ @Dannnno: The len(set(permutations(s))) method takes \$Θ(n·n!)\$ but the simple direct computation takes \$O(n^3 (\log n)^2)\$ which is asymptotically much better. (Note that there are ways to speed up the computation of multinomials but I didn't want to make it too complicated for the OP by going into this — I doubt that CodeWars requires that level of sophistication.) \$\endgroup\$ – Gareth Rees Jun 22 '16 at 12:20
  • \$\begingroup\$ I'd like to point out for inexperienced programmers who don't know about scientific notation, 5.3646042943000793e-05 means 5.3646042943000793 * pow(10, -5) or 0.000053646042943000793 \$\endgroup\$ – Pharap Jun 22 '16 at 21:18
14
\$\begingroup\$

You're looking for set(). The reason for your program being slow is:

  • you're calculating the permutation once: perm_repeated = permutations(string)
  • then you're looping through all the permutations (question: if you already have all the permutations in perm_repeated why are you doing again for p in permutations(string) instead of for p in perm_repeated?) and append them to a list
  • walk again through the list, eliminate the duplicates and append the result to another list.

You just created two lists for such an easy operation. What I'd do would be something like:

from itertools import permutations


def perms(some_string):
    perm_repeated = permutations(some_string)

    return len(set(perm_repeated))

In the above piece of code, I've just calculated all the permutations, then I returned the length of sets (unique values).

\$\endgroup\$
5
\$\begingroup\$

A few things:

  1. perm_set should use a set, not a list.
    This makes the if item not in perm_set \$O(1)\$ rather than \$O(n)\$.

  2. You should keep the perm_list as a list of tuples. You don't need the items to be strings, and so that conversion is somewhat useless.

  3. You don't need to create permutations twice. Even a small overhead could be the difference between pass and fail.

  4. You shouldn't print where it's not needed, the overhead to calling it is quite significant, definitely if you're calling it repetitively.

Changing these should result in:

def perms(obj):
    perm_set = set()
    for item in permutations(str(obj)):
        if item not in perm_set:
            perm_set.add(item)
    return len(perm_set)

From this we can see that, you can remove the if item not in perm_set as a set is unique. And so from that you should notice that the entire loop can simply become set(permutations(str(obj))). And so your final code should be something like:

def perms(obj):
    return len(set(permutations(str(obj))))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.