读后感：DFS解决全排列问题

原文链接

DFS解决全排列问题，从一道奥数题开始说起。http://www.jianshu.com/p/897f2a9e33cd

总结

有关全排列的题目可以通过DFS来解决。

• 最简单的例子
  • 题目：有数字1-9，求其全排列
  • 分析：
    想象有九个空位a[9]，现在第一个空位上填上一个数字，有多种选择，假设a[0] = 1；
    接下来在第二个空位上继续填数字，要求不与之前填过的数字相同（用book标记），则还剩下8个数字可以选择，假设a[1] = 2；
    依次类推，全部填满，打印。
    之后要退回一位，恢复book标记，选择其他数字，向下填空。
  • 伪代码

void dfs(int step){ //step表示当前要处理的盒子
      if(step == n+1){
            //输出排列
            for(i = 1; i <= n; i++)
                  printf("%d", a[i]);
            printf("\n");
            return;
      }
      for(int i = 1; i <= n; i++){
      if(book[i] == 0){
            a[step] = i;   //将i放入第step个空位
            book[i] = 1; // i已经被使用了
            dfs(step+1); //向下调用
            book[i] = 0; // 非常重要，收回该空位中的数字才能进行下一次尝试。
      }
  }
}

• DFS框架
  由上述分析，可发现过程类似DFS框架。DFS核心在于，对于每一个中可能性都尝试一遍，确定当前位的数字后，再以同样的方式调用下一位。
  伪代码：

void dfs(int step){
      *判断结束边界*
        尝试每一种可能 for(i = 1; i <= n; i++){
              尝试下一步 dfs(step + 1);
        }
    return; 
}

• 其他变形
  • 判断每一种可能——给定数组，空位选择不重复
    1-9可能变形为给定数组，则同样可以通过索引和book来选择数据；此外，还可以用swap来代替book，对于给定数组，在指定位可以与后面的数字交换，同样可以实现选择的功能。
    例子： [http://blog.csdn.net/ns_code/article/details/26509459
  • 重复数组中有重复的，求不同的排列
    额外开启一个unsorted_set用于记录当前位已经选择过的数字，如果再次遇到已经选择过的数字，则跳过。