perms_trace

See Erlang Programming, p. 199-200)

This is the second part of the program (see splits_trace).

1 perms([]) ->
2   [[]];
3 perms([X | Xs]) ->
4   [insert(X, As, Bs) || Ps <- perms(Xs), {As, Bs} <- splits(Ps)].

Before we proceed, we need to know two things:
 1. What are permutations
 2. How nested generators work
 
Permutations (key ideas):
 1. Order matters (e.g. [1,3,2] is different from [1,2,3])
 2. Number of arrangements is N! (e.g. N! = N * (N-1)!)

Nested generators:
    
 [ {X,Y} || X <- lists:seq(1,3), Y <- lists:seq(X,3) ]
      
 This list comprehension generates tuples containing pairs of Xs and Ys:
  [{1, 1}, {1, 2}, {3, 3}, {2, 2}, {2, 3}, {3, 3}]

 Each element of X generates a sequence of Ys. The list comprehension forms a tuple for each X and Y.

(Back to permutations)
    
Tracing perms([1]):
      
  perms([1 | [] = Xs]) ->
    [insert(1, As, Bs) || Ps <- perms(Xs), {As, Bs} <- splits(Ps)].
      perms([]) = [[]]                % a list containing an empty list
      splits([]) = {[] = As, [] = Bs} % see splits_trace
    [insert(1, [], [])]
    [[1]]
    
Tracing perms([1, 2]): 
    
  perms([1 | [2] = Xs]) ->
    [insert(1, As, Bs) || Ps <- perms(Xs), {As, Bs} <- splits(Ps)].
      perms([2]) = [[2]]                   % see previous trace
      splits([2]) = [{[], [2]}, {[2], []}] % see splits_trace
    [insert(1, [], [2]), insert(1, [2], [])]
  [[1,2], [2,1]]

Tracing perms([1, 2, 3]):

  perms([1 | [2,3] = Xs) ->
    [insert(1, As, Bs) || Ps <- perms(Xs), {As, Bs} <- splits(Ps)].
      perms([2,3]) = [[2,3], [3,2]] % see previous trace
      splits([2,3]) = [ {[], [2,3]}, {[2], [3]}, {[2,3], []} ]
      splits([3,2]) = [ {[], [3,2]}, {[3], [2]}, [[3,2], []} ]
    [insert(1, [], [2,3]), insert(1, [2], [3]), insert(1, [2,3], []),
      insert(1, [], [3,2]), insert(1, [3], [2]), insert(1, [3,2], [])]
  [[1,2,3], [2,1,3], [2,3,1], [1,3,2], [3,1,2], [3,2,1]]