DFS求全排列算法

本文主要是介绍DFS求全排列算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

版本1：非常像八皇后问题，请参见博客：https://blog.csdn.net/u011426016/article/details/88818754
八皇后要求不在同一行、同一列、以及同一条对角线上，这里只要求不在同一行，同一列即可。同一行自然不可能，因为每个皇后单独放置一行，同一列很好检查，使用visit数组标记即可，这种方法的优点是如果初始序列有序的话，可以保证全排列按字典序递增排列。

int a[5] = { 0, 1, 2, 3, 4 }, ans[5], vis[5], n = 4;
void dfs_1(int k){if (k == n + 1)cout << ans[1] << ans[2] << ans[3] << ans[4] << endl;else for (int i = 1; i <= n; i++){if (!vis[i]){ans[k] = a[i];vis[i] = 1;  //标记第i个数已经被使用dfs_1(k + 1);vis[i] = 0;  //释放标记，因为下次第k个数要做新的选择}}
}

重复元素，如果遇到重复元素稍微麻烦一点，比如1 2 2的全排列只有：1 2 2、2 1 2、2 2 1三种，如果用上述代码的话，会出现另外3中重复的情况，为了判断重复元素，我们可以记录下第k个数选择了什么元素，那么下次再重新选择第k个数的时候，我们可以判断当前选择元素是否跟上次选择的元素相同，如果相同则跳过。这是一个很重要的技巧，代码如下。

int a[5] = { 0, 1, 2, 2, 4 }, ans[5], vis[5], n = 4;
void dfs_2(int k){int mark = -1;  //用mark标记这一层我选择了什么元素if (k == n + 1)cout << ans[1] << ans[2] << ans[3] << ans[4] << endl;else for (int i = 1; i <= n; i++){if (!vis[i] && a[i] != mark){ //判断当前选择的元素，是否跟上次选择的相同，如果相同则跳过mark = a[i];              //如果不相同，则记录本次选择的元素ans[k] = a[i];vis[i] = 1;dfs_2(k + 1);vis[i] = 0;}}
}

版本2：基于交换的全排列算法，是各大博客讲的方法，基本思路是这样：对于n个数全排列，首先第1个数有n种选择，然后第2个数有n-1种选择，直到第n个数只有一种选择，这也是全排列公式：n! = n × (n-1) × (n-2) × …1的结果。那么问题是第1个怎么去选择n种，我们通过在初始序列中将第1个数跟[1-n]所有数字交换一遍即可实现第一个数的n种选取，第1个数选定后，第2个数同样，可以将第2个数跟[2-n]之间的所有数进行交换即可。

注意的是，每次交换后，当回溯回到第k层时，之前的交换要复原，目的是为了保证K之后的数据保持最初始的顺序，这样才能保证第k取遍[k-n]之间的所有数字而不重复。
举个栗子：
比如初始顺序是1 3 2，
括号中表示，基于上一个序列，第几个数跟第几个数交换：
(1)： 1 3 2， (1<->1, 2<->2, 3<->3）
(2)： 1 2 3， (1<->1, 2<->3, 3<->3）
(3)： 2 1 3， (1<->2, 2<->2, 3<->3）
(4)： 2 3 1， (1<->2, 2<->3, 3<->3）
(5)： 1 3 2， (1<->3, 2<->2, 3<->3）
(6)： 1 2 3， (1<->3, 2<->3, 3<->3）
第1位第一次跟自己交换取得1（上述(1)），然后第1位跟第2位交换得到2（上述(3)）最后跟第3位交换还是得到了1（上述(5)），这就是因为，每次回溯的时候，没有换回去，导致第1位重复取值，因此需要复原。

int a[5] = { 0, 1, 2, 2, 4 }, n = 4;
void swap(int& a, int& b){ int t = a; a = b; b = t; }
void perm(int s, int e){int mark = -1;if (s == e){cout << a[1] << a[2] << a[3] << a[4] << endl;}else for (int i = s; i <= e; i++){if (a[i] != mark){mark = a[i];swap(a[s], a[i]);perm(s + 1, e);swap(a[s], a[i]);}}
}

具体可以我的另一篇博客：http://blog.sina.com.cn/s/blog_73428e9a0102xyan.html
关于交换下图可以很好理解：第1位跟[1-8]交换可以取遍所有1-8，第2位：在第一位确定后，直接取遍剩余7个数据，第3位，可以取遍除了第1,2选定的数据之外的所有6个，…, 右图是某一个全排列：3 4 5 6 8 7 1 2，可以看到每一行的交换情况。

在这里插入图片描述
重复元素，跟上面类似：

int a[5] = { 0, 1, 2, 2, 4 }, n = 4;
void swap(int& a, int& b){ int t = a; a = b; b = t; }
void perm(int s, int e){int mark = -1;if (s == e){cout << a[1] << a[2] << a[3] << a[4] << endl;}else for (int i = s; i <= e; i++){if (a[i] != mark){mark = a[i];swap(a[s], a[i]);perm(s + 1, e);swap(a[s], a[i]);}}
}