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}.
Sorry the answer is not available at the moment…
If you are able to find the answer, please make sure to post it here. So that your Juniors have smile on their lips and feel happy.
Spread the 'tradition of sharing'.