What is the average case performance of this permutation-generating algorithm?

Question

I'm trying to determine the average case performance of this permutation-generating algorithm. It uses the recursive approach, in which the first element is swapped with each other element, producing a new set of permutations - these sets then go through the same routine, but with the first element fixed.

Here's the code in Python:

# Returns a list of all permutations of the given list.
def permutate(set):
    # A list of all found permutations, to be returned
    permutations = []

    # Takes a set which has all elements below index i fixed and finds all permutations
    def recurse(set, i):
        # If all elements are fixed, store the current permutation
        if i + 1 == len(set):
            permutations.append(set)
        else:
            # Swap the "first" element with each other element to generate new permutations
            for element in xrange(i, len(set)):
                set[element], set[i] = set[i], set[element]
                recurse(set, i + 1)
                set[element], set[i] = set[i], set[element]

    # Use the recursive algorithm to find all permutations, starting with no fixed elements
    recurse(set, 0)
    return permutations

print permutate([1, 2, 3])

I don't have much experience with analyzed recursive function performances, so I don't know how to solve this. If I had to make a guess, I would say that the runtime is Θ(n!), because a set with n elements has n! permutations (so there must be that much effort put in by the algorithm, right?)

Any help would be appreciated.

Answer 1

First of all, the complexity is O(n!) for the reason mentioned in the comment to the question.

But there are two other things.

1. Do not use set as a variable name, because you shadow a built-in data type

2. Your algorithm is not correct because of python implementation details

at the bottom of recursion, you append a resulting permutation to the permutations variable. But list in python is not passed by a value, so you actually append a reference to the input list. Because after recurse finishes its work, the input set is in the same order that it was at the beginning, so the permutation variable will store n! references to the same list. To fix that, you can use deepcopy method of copy module, the resulting code is (notice that you can stop resursion when i == len(s)):

import copy

# Returns a list of all permutations of the given list.
def permutate(s):
    # A list of all found permutations, to be returned
    permutations = []

    # Takes a set which has all elements below index i fixed and finds all permutations
    def recurse(s, i):
        # If all elements are fixed, store the current permutation
        if i == len(s):
            # append a deepcopy of s
            permutations.append(copy.deepcopy(s))
        else:
            # Swap the "first" element with each other element to generate new permutations
            for element in xrange(i, len(s)):
                s[element], s[i] = s[i], s[element]
                recurse(s, i + 1)
                s[element], s[i] = s[i], s[element]

    # Use the recursive algorithm to find all permutations, starting with no fixed elements
    recurse(s, 0)
    return permutations

print permutate([1, 2, 3])