previous | start | next

## 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