    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: }