Some problems require finding all permutations (different orderings) of

a set of items. For a set of n items { a1, a2, a3, . . . an } there are

n! permutations. For example, given the set {1, 2, 3} there are six

permutations:

{3, 2, 1} {2, 3, 1} {2, 1, 3} {3, 1, 2} {1, 3, 2} {1, 2, 3}

Write a recursive function that generates all the permutations of a set of

numbers. The general outline of a solution is given here, but the

implementation is up to you. The program will require storing a set of

permutations of numbers that you can implement in many ways (e.g.,

linked lists of nodes, linked lists of vectors, arrays, etc.) Your program

should call the recursive function with sets of several different sizes,

printing the resulting set of permutations for each.

One solution is to first leave out the nth item in the set. Recursively find

all permutations using the set of (n_1) items. If we insert the nth item

into each position for all of these permutations, then we get a new set of

permutations that includes the nth item. The base case is when there is

only one item in the set, in which case the solution is simply the

permutation with the single item.

For example, consider finding all permutations of {1, 2, 3}. We leave the

3 out and recursively find all permutations of the set {1, 2}. This consists

of the permutations:

{1, 2} {2, 1}

Next we insert the 3 into every position for these permutations. For the

first permutation, we insert the 3 in the front, between 1 and 2, and after

2. For the second permutation, we insert the 3 in the front, between 2

and 1, and after 1:

{3, 1, 2} {1, 3, 2} {1, 2, 3} {3, 2, 1} {2, 3, 1} {2, 1, 3}

The resulting six permutations comprise all permutations of the set

{1, 2, 3}.