First of all, the complexity is O(n!)
for the reason mentioned in the comment to the question.
But there are two other things.
Do not use
set
as a variable name, because you shadow a built-in data typeYour 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])