Some problem require finding all permutations (different orderings)of a set of items. For a set of n items there are n! permutations. For example, given the set {1, 2, 3} there are six permutations:
{1, 2, 3} {2, 3, 1} {2, 1, 3} {3, 1, 2}{1, 3, 2} {3, 2, 1}
Write a recursively function that generates all the permutations of a set of numbers. Use the STL set class for all set operations and the STL linked list class to store and manipulate each individual permutation. When creating a set containing lists, make. The general outline of a solution is given as followings:
The program will require storing a set of permutations of numbers that you can implement in many ways, (e.g., linked list, linked lists of vector, array, etc.)Your program should call the recursive function with sets of several different sizes, printing the resulting set of permutation 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 2 permutations:
{1, 2} {2, 1}
Now 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 1 and 2, and after 1.
{3, 1, 2} {1, 3, 2} {1, 2, 3} {3, 2, 1}{2, 3, 1} {2, 1, 3}
When creating a set containing lists, make sure to place a space between the last two >'s or the compiler may get confused. For
example, set > defines a set where elements are linked lists containing elements of type int. the code set >
without a space will likely produce a compiler error.
Use the following function declaration.
// Uses the permutations function to print all permutations of
// the first n whole numbers
voidprint_permutations(int n);
// Recursive function that returns a list contains all of the
// permutations of the given set of numbers
set>permutations(const set& numbers);
// Helper function for printing the contents of a list
voidprint_list(const list& v);
Sample Output
717: {6,5,4,2,1,3}
718: {6,5,4,2,3,1}
719: {6,5,4,3,1,2}
720: {6,5,4,3,2,1}
Permuations of {1,2,3,4,5} :
1: {1,2,3,4,5}
2: {1,2,3,5,4}
119: {5,4,3,1,2}
120: {5,4,3,2,1}
Permuations of {1,2,3,4} :
1: {1,2,3,4}
2: {1,2,4,3}
23: {4,3,1,2}
24: {4,3,2,1}
Permuations of {1,2,3} :
1: {1,2,3}
2: {1,3,2}
3: {2,1,3}
4: {2,3,1}
5: {3,1,2}
6: {3,2,1}
Permuations of {1,2} :
1: {1,2}
2: {2,1}
Permuations of {1}:
1: {1}
Permuations of {}:
Press any key to continue . . .