How do you generate all permutations of a list using recursion?
You pick one item to put in the first place, then you generate all the arrangements of the rest, and then you put the first item back on the front of each one.
def permutations(values):
if len(values) <= 1:
return [list(values)]
result = []
for index in range(len(values)):
rest = values[:index] + values[index + 1:]
for tail in permutations(rest):
result.append([values[index]] + tail)
return result
So how does it work? The function picks each item in turn to be the first one. For each choice it removes that item from the list, and then it calls itself with the smaller list to get all the arrangements of the rest. And then it puts the chosen item on the front of each of those arrangements.
And the stopping condition is the list with one item in it or no items in it. Then there is exactly one arrangement, which is the list itself.
And the size of the answer is the important fact. A list of n items has n factorial arrangements, because there are n choices for the first place, then n minus one for the second, and so on. So three items have six arrangements, four items have twenty-four, and seven items have more than five thousand.
the items the arrangements
----------- ------------------
1 1
3 6
4 24
7 5,040
10 3,628,800
So the complexity is O of n times n factorial for the time, and the same for the space, because the answer holds every arrangement and every arrangement holds n items. And the growth is much faster than the subsets, so a question about permutations only makes sense for a small list.
And this is worth knowing about. A common interview question asks for the arrangements of a list where some items are the same, and then the answer is smaller because the repeats give the same arrangement over and over.
So the rule to remember is this. Pick the first item, arrange the rest, and then put the first item back on the front.
The next two questions in this topic show the library helper and the version that handles repeats.