一、开篇
Permutation，排列问题。这篇博文以几道LeetCode的题目和引用剑指offer上的一道例题入手，小谈一下这种类型题目的解法。
二、上手
最典型的permutation题目是这样的：
Given a collection of numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
}
};
我第一次接触这类问题是在剑指offer里，见笔记 面试题 28(*)，字符串的排列(排列问题的典型解法：采用递归，每次交换首元素和剩下元素中某一个的位置) 。
书中对这种问题采用的方法是“交换元素”，这种方法的好处是不需要再新开一个数组存临时解，从而节省一部分辅助空间。
交换法的思路是for(i = start to end)，循环中: swap (第start个和第i个)，递归调用(start+1)，swap back
根据这个思路，可以轻易写出这道题的代码：
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
if(num.size() == ) return res;
permuteCore(num, );
return res;
}
private:
vector<vector<int> > res;
void permuteCore(vector<int> &num, int start){
if(start == num.size()){
vector<int> v;
for(vector<int>::iterator i = num.begin(); i < num.end(); ++i){
v.push_back(*i);
}
res.push_back(v);
}
for(int i = start; i < num.size(); ++i){
swap(num, start, i);
permuteCore(num, start+);
swap(num, start, i);
}
}
void swap(vector<int> &num, int left, int right){
int tmp = num[left];
num[left] = num[right];
num[right] = tmp;
}
};
permutation II 是在上一题的基础上，增加了“数组元素可能重复”的条件。
这样，如果用交换法来解，需要定义一个set来存储已经交换过的元素值。
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
if(num.size() <= ) return res;
permCore(num, );
return res;
}
private:
vector<vector<int> > res;
void permCore(vector<int> &num, int st){
if(st == num.size()) res.push_back(num);
else{
set<int> swp;
for(int i = st; i < num.size(); ++i){
if(swp.find(num[i]) != swp.end()) continue;
swp.insert(num[i]);
swap(num, st, i);
permCore(num, st+);
swap(num, st, i);
}
}
}
void swap(vector<int> &num, int left, int right){
int tmp = num[left];
num[left] = num[right];
num[right] = tmp;
}
};
题外话：交换法只是解法的一种，其实我们还可以借鉴Next permuation的思路(见这个系列的第二篇)来解这一道题，从而省去了使用递归。
使用Next permutation的思路来解 Permutation II
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
if(num.size() <= ) return res;
sort(num.begin(), num.end());
res.push_back(num);
int i = , j = ;
while(){
//Calculate next permutation
for(i = num.size()-; i >= && num[i] >= num[i+]; --i);
if(i < ) break;
for(j = num.size()-; j > i && num[j] <= num[i]; --j);
swap(num, i, j);
j = num.size()-;
++i;
while(i < j)
swap(num, i++, j--);
//push next permutation
res.push_back(num);
}
return res;
}
private:
vector<vector<int> > res;
void swap(vector<int> &num, int left, int right){
int tmp = num[left];
num[left] = num[right];
num[right] = tmp;
}
};
三、应用
Permutation类问题一个典型的应用就是N皇后问题，以LeetCode上的n-queens题和 n-queens II 为例：
n-queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."], ["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
}
};
上面是题 n-queens 的内容，题 n-queens II 其实反而更容易，它要求不变，只是不需要返回所有解，只要返回解的个数。
有了上面的思路，如果用A[i] = j 表示第i 行的皇后放在第j列上，N-queen也是一个全排列问题，只是排列时需要加上一个额外判断，就是两个皇后是否在一条斜线上。
真正实现的时候我犯了一个错误。
如上所说，交换法的思路是for(i = start to end)，循环中: switch(第start个和第i个)，递归调用(start+1)，switch back
我错误的认为N皇后不需要switch back，其实 switch back是必须要做的步骤，因为这种解法的本质是还是深搜，子递归会层层调用下去，不及时swtich back的话，当前层的下一次递归调用会把重复的值switch过来，从而出现重复，结果是漏掉了一些正确的排列方法。因此，使用交换法解全排列问题时，不可打乱递归调用时的排列。
题N-Queens被AC的代码：
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
if(n <= ) return res;
int* A = new int[n];
for(int i = ; i < n; ++i) A[i] = i;
nqueensCore(A, , n);
return res;
}
private:
vector<vector<string> > res;
void nqueensCore(int A[], int start, int n){
if((start+) == n && judgeAttackDiag(A, start))
output(A, n);
else{
for(int i = start; i < n; ++i){
swtich(A, start, i);
if(judgeAttackDiag(A, start))
nqueensCore(A, start+, n);
swtich(A, start, i);
}
}
}
void swtich(int A[], int left, int right){
int temp = A[left];
A[left] = A[right];
A[right] = temp;
}
bool judgeAttackDiag(int A[], int newPlace){ //everytime a new place is configured out, judge if it can be attacked by the existing queens
if(newPlace <= ) return true;
bool canAttack = false;
for(int i = ; i < newPlace; ++i){
if((newPlace - i) == (A[newPlace] - A[i]) || (i - newPlace) == (A[newPlace] - A[i])) canAttack = true;
}
return !canAttack;
}
void output(int A[], int n){
vector<string> v;
for(int i = ; i < n; ++i){
string row(n,'.');
v.push_back(row);
}
for(int j = ; j < n; ++j){
v[A[j]][j] = 'Q';
}
res.push_back(v);
}
};
N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
class Solution {
public:
int totalNQueens(int n) {
}
};
基本思路依然是使用全排列，这次代码可以写得简洁一些。
class Solution {
public:
int totalNQueens(int n) {
if(n <= ) return n;
res = ;
queens = new int[n];
for(int i = ; i < n; queens[i] = i, ++i);
nQueensCore(queens, n, );
return res;
}
private:
int res;
int* queens;
void nQueensCore(int* queens, int n, int st){
if(st == n) ++res;
int tmp, i, j;
for(i = st; i < n; ++i){
tmp = queens[st];
queens[st] = queens[i];
queens[i] = tmp;
for(j = ; j < st; ++j){
if(abs(queens[st] - queens[j]) == abs(st - j)) break;
}
if(j == st) nQueensCore(queens, n, st+);
tmp = queens[st];
queens[st] = queens[i];
queens[i] = tmp;
}
}
};
我第一次提交时依然犯了忘掉switch back的错误，第一次提交的代码中，写的是“if(abs(queens[st] - queens[j]) == abs(st - j)) return;"
这样就导致了switch back部分代码(高亮部分)不会被执行，从而打乱了整个顺序。
3. 数独问题
数独和N 皇后一样，都是需要不停地计算当前位置上所摆放的数字是否满足条件，不满足就回溯，摆放另一个数字，基于这个新数字再计算。
选择新数字的过程，就是全排列的过程。
以LeetCode上的例题为例:
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
void solveSudoku(vector<vector<char> > &board) {}
关于数独的规则，请参见这里：Sudoku Puzzles - The Rules. 必须保证每行，每列，和9个3X3方块中1-9各自都只出现一次。
我们依然可以用交换法来解，思路依然是：
for(i = start to end)，循环中: swap (第start个和第i个)；如果当前排列正确，递归调用(start+1)；swap back
这里需要额外考虑的是：数独阵列中有一些固有数字，这些数字是一开始就不能动。因此，我用flag[][]来标记一个位置上的数字是否可替换。flag[i][j] == true表示Board[i][j]上的数字可替换，false表示不可替换。因此思路稍加变更，成了：
Func(start){
a. 如果 flag上start对应的位置 == false，说明当前位不能改动，因此只需判断当前排列是否正确，正确则递归调用(start+1)
b. flag上start对应的位置 = false
c. for(i = start 到当前行末尾)，循环中: swap (第start个和第i个)；如果当前排列正确，递归调用(start+1)；swap back
d. flag上start对应的位置 = true
}
代码：
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
flag = new bool*[]; //flag[i][j] == false means value on board[i][j] is decided or originally given.
digits = new bool[]; //digits is used to check whether one digit (1-9) is duplicated in sub 3*3 square
int i = , j = ;
for(; i < ; ++i){
flag[i] = new bool[];
for(j = ; j < ; ++j){
if(board[i][j] == '.') flag[i][j] = true;
else flag[i][j] = false;
}
}
initialBoard(board, ); //初始化Board，先把所有的空缺填满，填的时候先保证每一行没有重复数字。
solveSudokuCore(board, );
}
private:
bool **flag;
bool *digits;
void initialBoard(vector<vector<char> > &board, int N){
int i, j, k;
bool *op = new bool[N+];
for(i = ; i < N; ++i){
for(j = ; j <= N; ++j) op[j] = false;
for(j = ; j < N; ++j){
if(board[i][j] != '.') op[board[i][j] - ''] = true;
}
for(j = , k = ; j < N; ++j){
if(board[i][j] == '.'){
while(op[k++]);
board[i][j] = ((k-) + '');
}
}
}
delete op;
}
bool check(vector<vector<char> > &board, int index){
int col = index%, row = index/;
int i = ;
for(i = ; i < ; ++i){
if(i != row && !flag[i][col] && board[i][col] == board[row][col])
return false;
}
if((col+)% == && (row+)% == ){
for(i = ; i < ; ++i) digits[i] = false;
for(int j = (row/)*; j < (row/+)*; ++j){
for(int k = (col/)*; k < (col/+)*; ++k){
if(digits[board[j][k] - '']) return false;
digits[board[j][k] - ''] = true;
}
}
}
return true;
}
bool solveSudokuCore(vector<vector<char> > &board, int index){
if(index == ) return true;
if(!flag[index/][index%]){ //如果当前位置是不可更改的，那么只要check一下是否正确就可以了
if(check(board, index) && solveSudokuCore(board, index+))
return true;
}else{ //如果当前位置是可更改的，那么需要通过交换不停替换当前位，看哪一个数字放在当前位上是正确的。
flag[index/][index%] = false;
for(int i = index; i < (index/+)*; ++i){
if(flag[i/][i%] || i == index){
int tmp = board[i/][i%];
board[i/][i%] = board[index/][index%];
board[index/][index%] = tmp;
if(check(board, index) && solveSudokuCore(board, index+))
return true; //如果当前位上放这个数字正确，那么继续计算下一位上该放哪个数字。
tmp = board[i/][i%];
board[i/][i%] = board[index/][index%];
board[index/][index%] = tmp;
}
}
flag[index/][index%] = true;
}
return false;
}
};
四、引申
给定一个包含重复元素的序列，生成其全排列
如果要生成全排列的序列中包含重复元素，该如何做呢？以LeetCode上的题 Permutations II 为例：
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1].
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
}
};
思路：
比如[1, 1, 2, 2]，我们交换过一次 位置1上的"1"和 位置3上的"2"，就不再需要交换 位置1上的"1" 和 位置4上的"2"了。
因此，在传统的交换法的基础上，需要加一个过滤：比如当前我们 需要挨个将位置 2-4的元素和位置1上的"1" 交换，此时，如果2-4上的元素有重复值，我们只需要用第一次出现的那个值和位置1做交换即可。
我开始的思路是：先将位置2-4的元素sort一下，然后定义pre存放上次交换的元素的值，如果当前值和pre不同，则交换当前值和位置1上的值。
按照这种方式实现的代码是：
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
if(num.size() == ) return res;
permuteCore(num, );
return res;
}
private:
vector<vector<int> > res;
void permuteCore(vector<int> &num, int start){
if(start == num.size()){
vector<int> v;
for(vector<int>::iterator i = num.begin(); i < num.end(); ++i){
v.push_back(*i);
}
res.push_back(v);
}
sort(num.begin()+start, num.end());
int pre;
for(int i = start; i < num.size(); ++i){
if(i == start || pre != num[i]){
swap(num, start, i);
permuteCore(num, start+);
swap(num, start, i);
pre = num[i];
}
}
}
void swap(vector<int> &num, int left, int right){
int tmp = num[left];
num[left] = num[right];
num[right] = tmp;
}
};
然而判定结果是 Output Limit Exceeded，分析了一下原因，在于Sort破坏了当前子排列，导致出现了重复解。正如我上一节中所说，使用交换法解全排列问题时，不可打乱递归调用时的排列，不然可能导致重复解。
不用sort来做判断的话，那就使用set 来去重吧。将上面代码的高亮部分换成下面代码的高亮部分，这次就AC了。
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
if(num.size() == ) return res;
permuteCore(num, );
return res;
}
private:
vector<vector<int> > res;
void permuteCore(vector<int> &num, int start){
if(start == num.size()){
vector<int> v;
for(vector<int>::iterator i = num.begin(); i < num.end(); ++i){
v.push_back(*i);
}
res.push_back(v);
}
set<int> used;
for(int i = start; i < num.size(); ++i){
if(used.find(num[i]) == used.end()){
swap(num, start, i);
permuteCore(num, start+);
swap(num, start, i);
used.insert(num[i]);
}
}
}
void swap(vector<int> &num, int left, int right){
int tmp = num[left];
num[left] = num[right];
num[right] = tmp;
}
};
但这种解法的缺点在于比较费空间，set 需要定义在局部变量区，这样才能保证递归函数不混用set。
五、总结：
对于全排列问题，交换法是一种比较基本的方法，其优点就在于不需要额外的空间。
使用时需要注意
a. 不要打乱子问题的序列顺序。
b. 记得换回来，回溯才能正确进行，也就是说，负责switch back部分的代码必须被执行到。