From Backtracking to Factorial Coordinates: Understanding Permutations Deeply

Most developers learn permutation generation through recursion and swapping.
It works, it's elegant… but it often feels a bit magical.

This article goes much deeper.

We will:

• Fully understand how backtracking actually works
• Build a precise mental model of recursion
• Discover that permutations form a structured coordinate space
• Eliminate recursion entirely using factorial number systems (Lehmer code)
• Derive efficient, controllable, high-performance implementations

1. The Classical Backtracking Algorithm

Here is the standard implementation:

  Copy
  
template <typename T>
void permuteHelper(std::vector<T>& vec, int start, std::vector<std::vector<T>>& result) {
    if (start >= vec.size()) {
        result.push_back(vec);
        return;
    }

    for (int i = start; i < vec.size(); ++i) {
        std::swap(vec[start], vec[i]);
        permuteHelper(vec, start + 1, result);
        std::swap(vec[start], vec[i]); // backtrack
    }
}
  
  

2. The First Misconception

A very common intuition is:

"A swap creates a permutation"

This is wrong.

Reality:

• A swap = a choice
• Recursion = completing that choice
• Base case = validating the permutation

3. The Real Meaning of start

start is not just an index.

It represents:

  Copy
  
How many positions are already fixed
  
  

4. Why We Push at the Base Case

  Copy
  
if (start >= vec.size()) {
    result.push_back(vec);
}
  
  

This is the only correct place to store a permutation. Because only here:

  Copy
  
All positions are fixed
  
  

Everything before that is just partial construction.

5. The Hidden Tree Structure

The algorithm is actually exploring a tree:

  Copy
  
position 0 → choose element
  position 1 → choose element
    position 2 → choose element
      ...
        → complete → store
  
  

6. The First Permutation Mystery

Why is [1,2,3,4,5] the first result? Because the algorithm always tries:

  Copy
  
i = start
  
  

Which means:

  Copy
  
swap(start, start) → no change
  
  

So the first path is:

  Copy
  
[1,2,3,4,5] → unchanged all the way down → pushed (because always i == start)
  
  

7. The Key Insight: Subtrees Have Identity Paths

Example:

  Copy
  
swap(0,1) → [2,1,3,4,5]
  
  

Then:

  Copy
  
start = 1 → no swaps
start = 2 → no swaps
...
  
  

So we get:

  Copy
  
[2,1,3,4,5]
  
  

This reveals something deep:
Every subtree has a path where nothing changes further.

8. From Tree to Coordinates

Each recursive path corresponds to a sequence:

  Copy
  
i₀, i₁, i₂, ..., iₙ₋₁
  
  

Where:

  Copy
  
iₖ ∈ [k, n-1]
  
  

Normalize:

  Copy
  
cₖ = iₖ - k
  
  

Now:

  Copy
  
c₀ ∈ [0, n-1]
c₁ ∈ [0, n-2]
...
cₙ₋₁ = 0
  
  

9. This Is a Number System

These cₖ form a number in:

  Copy
  
factorial base (mixed radix)
  
  

Example for n = 3:

10. Backtracking = Counting

The recursion is actually doing:

  Copy
  
for c₀ in [0..n-1]
  for c₁ in [0..n-2]
    ...
      emit permutation
  
  

This is just counting:

  Copy
  
0 → 1 → 2 → ... → n! - 1
  
  

11. Killing the Tree

Instead of exploring all possibilities:
We can directly follow one path.

At level k:

  Copy
  
i = k + c[k]
  
  

12. Direct Construction (No Branching)

  Copy
  
template <typename T>
std::vector<T> buildPermutation(std::vector<T> vec, const std::vector<int>& c) {
    int n = vec.size();

    for (int k = 0; k < n; ++k) {
        int i = k + c[k];
        std::swap(vec[k], vec[i]);
    }

    return vec;
}
  
  

13. Converting Index → Permutation

We convert integer k into factorial base:

  Copy
  
std::vector<int> toFactorialBase(int k, int n) {
    std::vector<int> c(n);

    for (int i = 1; i <= n; ++i) {
        c[n - i] = k % i;
        k /= i;
    }

    return c;
}
  
  

14. Full k-th Permutation

  Copy
  
template <typename T>
std::vector<T> kthPermutation(std::vector<T> elements, int k) {
    auto c = toFactorialBase(k, elements.size());
    return buildPermutation(elements, c);
}
  
  

15. Performance Comparison

16. Mental Model Summary

  Copy
  
Backtracking:
    explore tree

Coordinates:
    follow path

Factorial system:
    index permutations
  
  

17. Deep Insight

A permutation is not just an arrangement.
It is a coordinate in a structured space.

18. Practical Uses

• Parallel permutation search
• Optimization problems (TSP, scheduling)
• Procedural generation
• Deterministic randomness
• Memory-efficient enumeration

19. Final Takeaway

Backtracking explores permutations.
Factorial encoding defines them.

Once you see permutations as coordinates:

• recursion becomes optional
• control becomes explicit
• performance becomes predictable