/*
 * CS2S03/SE2S03, October 2011
 * Assignment 4, Question 1
 * File: PE0605.cpp
 * ----------------
 * This program lists the permutations of a string of upper case letters,
 * possibly with repeating letters.
 */ 
     
 /* libraries */  
 #include <iostream>   
 #include "simpio.h"   
 #include "genlib.h"   
     
/* private function prototypes */
void ListPermutations(string str);
void RecursivePermute(string prefix, string rest, int* ptr);
     
 /* main program */  
 int main() {   
    string str;

    cout << "This program lists all permutations of a string." << endl;
    cout << "Enter a string (upper case letters): ";
    str = GetLine();

    ListPermutations(str);
	
	return 0;    
 }

/* Function: ListPermutations
 * Usage: ListPermutations(s);
 * ---------------------------
 * This function lists all permutations of a string of upper case letters,
 * with possible repeated letters.
 */

 void ListPermutations(string str) {
     int count = 0;
     RecursivePermute("", str, &count);
	 cout << endl;
	 cout << "Total of " << count << " permutations." << endl;
 }
  
/*
 * Function: RecursivePermute
 * Usage: RecursivePermute(prefix, rest, &n);
 * --------------------------------------
 * Recursive implementation of ListPermutations using prefix and rest.
 */
 
void RecursivePermute(string prefix, string rest, int* ptr) {
    if (rest == "") {
        *ptr += 1;
        cout << prefix << endl;
    } else {
        for (int i = 0; i < rest.length(); i++) {
            /* if it is the first appearance of rest[i] */
			if (rest.find(rest[i]) == i) {
			    string newPrefix = prefix + rest[i];
                string newRest = rest.substr(0, i) + rest.substr(i+1);
                RecursivePermute(newPrefix, newRest, ptr);
            }
        }
	}
}