Permutation

April 29, 2024 · 3 min read

Non Traditional Engineer

Permutation is an important idea in math, but surprisingly, it is also an important idea in computer science. I mean... permutation itself is not important ... Dont worry, you wont see them in your cs exams. However, it yields an important idea of backtracking.

Backtracking

is a general algorithmic technique that involves incrementally building up a solution to a computational problem, then abandoning (or "backtracking" from) each partial solution ("candidate solution") as soon as it is determined not to be a viable solution to the problem at hand. This method is used extensively in problems related to constraint satisfaction, such as puzzles (like Sudoku), combinatorial optimization problems, and in scenarios requiring the exploration of all possible configurations, such as parsing and the placement of game pieces.

Here’s a general outline of how backtracking works:

Choose: Begin at a starting point and choose an option to advance the solution.
Constraint Check: After choosing an option, check if the partial solution meets the problem constraints.
Goal Check: Determine if a complete solution has been formed. If so, output or store this solution.
Further Exploration: If the current partial solution is valid but incomplete, extend the solution further by choosing the next option.
Backtrack: If an option leads to a dead end (i.e., it violates constraints or no further extension is possible), discard this option and return to the previous step, trying other possible options.

The process repeats recursively, exploring all possible paths until a solution is found or all paths are deemed unviable. This technique effectively prunes large portions of the search space that cannot possibly lead to a solution, making it efficient for solving some types of complex problems that would otherwise be infeasible to handle through brute-force methods.

Here is a very interesting example... Could you figure it out?

#include <iostream>
#include <vector>

using namespace std;


/**
 * @brief print permutation for number 0 to num-1 with num digits
 * 
 * @param num 
 */
vector<int> res;

void helper(int idx, int num) {
  if (idx == num) {
    for (auto i: res) {
      cout << i << " ";
    }
    cout << endl;
    return;
  }

  for (int i = 0; i < num; i++) {
    res.push_back(i);
    helper(idx + 1, num);
    res.pop_back();
  }
}

void permutation(int num) {
  helper(0, num);
}

int main() {
  int a = 0;
  cin >> a;
  permutation(a);
}

You can copy and paste these code and play with it~

Have fun and happy coding.

Backtracking​

Backtracking