Recursion

Permutations

To carry out the ideas in the previous slide, we implement a loop that creates a shorter word that omits the current position.

vector<string> generate_permutations(string word)
{
   vector<string> result;
   ...
   for (int i = 0; i < word.length(); i++)
   {
      string shorter_word = word.substr(0, i)
         + word.substr(i + 1, word.length() - i - 1);
      ...
   }
   return result;
}

The next step is to compute the permutations of the shorter word.

vector<string> shorter_permutations
   = generate_permutations(shorter_word);

For each of the short permutations, add the omitted letter.

for(int j = 0; j < shorter_permutations.size(); j++)
{
   string longer_word = word[i] + shorter_permutations[j];
   result.push_back(longer_word);
}

You must build in a stopping point for the recursion, as a special case to handle words of length 1.
```
if (word.length() == 1)
{
   result.push_back(word);
   return result;
}
```

previous | start | next