01: #include <iostream>
02: #include <string>
03: #include <vector>
04: 
05: using namespace std;
06: 
07: /**
08:    Computes n!
09:    @param n a nonnegative integer
10:    @return n! = 1 * 2 * 3 * . . . * n
11: */
12: int factorial(int n)
13: {
14:    if (n == 0) return 1;
15:    int smaller_factorial = factorial(n - 1);
16:    int result = smaller_factoria * n;
17:    return result;
18: }
19: 
20: /**
21:    Generates all permutations of the characters in a string
22:    @param word a string
23:    @return a vector that is filled with all permutations 
24:    of the word
25: */
26: vector<string> generate_permutations(string word)
27: {
28:    vector<string> result;
29:    if (word.length() == 1) 
30:    {
31:       result.push_back(word);
32:       return result;
33:    }
34: 
35:    for (int i = 0; i < word.length(); i++)
36:    {
37:       string shorter_word = word.substr(0, i)
38:          + word.substr(i + 1, word.length() - i - 1);
39:       vector<string> shorter_permutations
40:          = generate_permutations(shorter_word);
41:       for (int j = 0; j < shorter_permutations.size(); j++)
42:       {
43:          string longer_word = word[i] + shorter_permutations[j];
44:          result.push_back(longer_word);
45:       }   
46:    }
47:    return result;
48: }
49: 
50: int main()
51: {
52:    cout << "Enter a string: ";
53:    string input;
54:    getline(cin, input);   
55:    cout << "There are " << factorial(input.length()) 
56:       << "permutations.\n";
57:    vector<string> v = generate_permutations(input);
58:    for (int i = 0; i < v.size(); i++)
59:       cout << v[i] << endl;
60:    return 0;
61: }