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:
def permutations(s):
if(s == []): return [[]]
ret = []
for k in permutations(s[1:]):
for i in range(len(k)+1):
ret.append(k[0:i] + [s[0]] + k[i:])
return ret
Testing it with a simple example:
> print(permutations([1,2,3]))
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]
This confirms the code is correct.