permutation program

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 <list<int> > defines a set where elements are linked

lists containing elements of type int. the code set <list<int>>

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

void print_permutations(int n);

// Recursive function that returns a list contains all of the

// permutations of the given set of numbers

set<list <int> >permutations(const set<int>& numbers);

// Helper function for printing the contents of a list

void print_list(const list<int>& 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 . . .