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.