Time complexity of string permutation algorithm

Question

I wrote a simple algorithm to return a list of all possible permutations of a string, as follows:

def get_permutations(sequence):

'''
Enumerate all permutations of a given string

sequence (string): an arbitrary string to permute. Assume that it is a
non-empty string.

Returns: a list of all permutations of sequence
'''

if len(sequence) <= 1:
    return list(sequence)
else:
    return_list = get_permutations(sequence[1:])
    new_list = []
    for e in return_list:
        for pos in range(len(e) + 1):
            new_list.append(e[:pos] + sequence[0] + e[pos:])
return new_list

From this code I'm seeing a time complexity of O(n* n!), O(n!) is the increasing tendency for the number of elements "e" in the "return_list", and there's a nested loop that increases linearly with each new recursion, so from my understanding, O(n). The conclusion is that the algorithm as a whole has O(n*n!) complexity.

However, when searching for similar solutions I found many threads saying the optimal case for this type of algorithm should be only O(n!), so my question is:

Am I missing something on my complexity analysis or is my code not optimal? And if it isn't, how can I properly correct it?

Answer 1

I think your algorithm is O(n * n!) because to calculate a permutation of a string x of length n, your algorithm will use the permutations of a sub string of x, which is x without the first character. I'll call this sub string y. But to calculate the permutations of y, the permutations of a sub string of y will need to be calculated. This will continue until the sub string to have its permutations calculated is of length 1. This means that to calculate the permutations of x you will need to calculate the permutations of n - 1 other strings.

Here is an example. Let's say the input string was "pie". Then what your algorithm does is it takes "pie" and calls its self again with "ie", after which it calls itself with "e". Because "e" is of length 1 it returns and all the permutations for "ie" are found which are "ie" and ei". Then that function call will return the permutations of "ie" and it is only at this point that the permutations of "pie" are calculated which it does using the permutations of "ie".

I looked up a permutation generating algorithm called Heap's algorithm that has a time complexity of O(n!). The reason it has a time complexity of n! is because it generates permutations using swaps and each swap that it does on an array generates a unique permutation for the input string. Your algorithm however, generates permutations of the n-1 sub strings of the input string which is where the time complexity of O(n * n!) comes from.

I hope this helps and sorry if I'm being overly verbose.

Answer 2

Take any algorithm that generates and then prints out all permutations of a sequence of n different elements. Then, since there are n! different permutations and each one has n elements, simply printing out all the permutations will take time Θ(n · n!). That's worth keeping in mind as you evaluate the cost of generating permutations - even if you could generate all permutations in time O(n!), you couldn't then visit all those permutations without doing O(n · n!) work to view them all.

That being said - the recursive permutation-generating code you have up above does indeed run in time Θ(n · n!). There are some other algorithms for generating permutations that can generate but not print the permutations in time Θ(n!), but they work on different principles.

I have found, empirically, that unless you see a careful runtime analysis of a permutation-generating algorithm, you should be skeptical that the runtime is Θ(n!). Most algorithms don't hit this runtime, and in the cases of the ones that do, the analysis is somewhat subtle. Stated differently - you're not missing anything; there's just lots of "on the right track but incorrect" claims made out there. :-)