CS 141 - Lab 3

Permutations

Directions

Find a partner. Solve the following programming problem in C++. When you finish, turn it in electronically, one copy per team. When you are done, you should work on Homework 2 or Programming Assignment 2.

Overview

Given a list of letters, output all of the permutations of those letters, without repeats.

Input Spec

Read in a single integer: this is the number of cases (letter sets) you will do on this run of the program. (1 int)

For each letter set, read in a single string.

Continue with the next case.

Output Spec

Your output must match exactly the following, including whitespace.

Print out in alphabetic order the permutations of the letters for each set, one per line. Repeats are not allowed.

Testing

Test cases can be found here. Run these using regular UNIX redirection & testing:

./lab3 < inputFile | diff - outputFile

Where inputFile and outputFile will be one of these or a pair of your own creation.
lab3test1.in lab3test1.out
lab3test2.in lab3test2.out
If the testing line above produces no output when run with these tests, then you have completed the program.

Recommended Approach

This is a highly recursive problem. A good recursive call for this could look like:
```
set<string> permute(string toPermute, string prefix);
```
This would be: permute every character in the string "toPermute" and return me those permutations with the string "prefix" added to the beginning of each permutation. Thus
```
permute("ab", "foo");
```
would output the set {"fooab", "fooba"};
The STL set datatype is your friend: it will give you the uniqueness and the sorted output properties for free.
Actually inserting and removing characters from the string toPermute is tricky. You might want to "remove" the characters by replacing them with a known invalid character, like " ". If you do this, it is a little more tricky to check if toPermute is "empty" for your base case.