List permutations

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.