Step 2 of 6

Permutations

A permutation is an ordering: abc, acb, bac, bca, cab and cba are the 6 orderings of three letters. Here each level of the decision tree answers "which letter goes in the next position?", and a letter can't be used twice, so the search keeps a used flag per letter.

Every backtracking function has the same three moves, often called choose, explore, un-choose:

#include <iostream>
#include <string>
#include <vector>

void permute(const std::string& s, std::vector<bool>& used, std::string& cur) {
    if (cur.size() == s.size()) {          // every position filled
        std::cout << cur << "\n";
        return;
    }
    for (std::size_t i = 0; i < s.size(); i++) {
        if (used[i]) continue;             // already placed
        used[i] = true;                    // choose
        cur.push_back(s[i]);
        permute(s, used, cur);             // explore
        cur.pop_back();                    // un-choose
        used[i] = false;
    }
}

int main() {
    std::string s = "abc";
    std::vector<bool> used(s.size(), false);
    std::string cur;
    permute(s, used, cur);
}

abc
acb
bac
bca
cab
cba

How it works

• The loop offers every letter that isn't used yet as the next character. With n letters the first level has n choices, the next n - 1, and so on, so there are n! permutations: 6 for 3 letters, 3,628,800 for 10.
• Un-choosing restores both pieces of state (cur and used) in the reverse order they were changed. Forget either and later branches start from a corrupted state.
• Because the loop tries letters in the order they appear, and "abc" is sorted, the output comes out in alphabetical (lexicographic) order.

Repeated letters

Run this on "aab" and you get aab, aba, aab, aba, baa, baa: every result twice, because the two a's are treated as different letters. The fix is to choose among distinct letters instead of positions. Count how many of each letter you have (a: 2, b: 1). At each position, loop over the letters that still have a count above zero, use one (count - 1), explore, then give it back (count + 1). Two identical letters are now the same single choice, so each different string is built exactly once. If you loop over the letters in alphabetical order (a std::map does that), the results come out sorted too.

The standard library has std::next_permutation, which steps a sorted range through its orderings in lexicographic order, skipping duplicates. Use it in real code; here, build the search yourself.

Your turn: write unique_permutations(s), returning each distinct ordering of the letters in s exactly once, in lexicographic order.

Previous: Subsets and the decision tree Next: Pruning