List permutations

Posted on March 7, 2013

Last updated on March 6, 2013

Problem Statement:

Generate all the permutations of a list

This is another rather simple interview-type question, quite similar in spirit to that of generating the power set.

Imagine a list $$L$$, and an element $$x_i$$. Generate all the possible permutations of $$L - x_i$$. Then, intersperse $$x_i$$ into every possible position for every element of the permutations of $$L - x_i$$.

For example, given a list [1,2], take the sublist [2], and generate a list of all possible permutations, [[2]]. Now, add the element 1 into every possible position for [2], that is at index $$0$$ and at index $$1$$. This generates the list [[1,2],[2,1]], our required answer.

We turn the above into a simple Python code:

Testing it with a simple example:

This confirms the code is correct.

Markdown SHA1: 98176e2c1520e143a1539e4e50ebe422f1808329