C++实现全排列

字符串集合的笛卡尔乘积
本周项目中有这么一个问题，给定集合 A = {‘0’, ‘1’}，则A * A = {‘00’, ‘01’, ‘10’, ‘11’}，即笛卡尔乘积，这个可以用两层循环简单的实现：

for (int i = 0; i < A.size(); i++) {
	for (int j = 0; j < A.size(); j++) {
		A[i] + A[j];
	}
}

但是如果要求A^n，且n很大或者不确定的情况下，我们就需要用回溯法来实现，每次深度优先搜索都有一个搜索树，每个树节点都保存了一个状态，我们来对问题进行建模，A ^ n的元素肯定是长度为n的字符串，即长度为 n 的字符数组，我们可以通过对数组的从左到右，每个位置填充A的元素，填充n次，即可以得到1个元素。当到达末尾时，不能在继续了，则返回上一个格子，选择另外的元素填充。

// src为源集合，dest为目标集合，cur_str为当前节点状态，cur为当前要填第几个格子，n为总共有多少个格子
void repeat_string_recursive(vector<string> &src, vector<string> &dest, string cur_str, int cur, int n)
{
    if (cur == n) { //当cur = n时，则表示到达末尾，添加一个元素
        dest.push_back(cur_str);
        return ;
    }
    for (int i = 0; i < src.size(); i++) { // 在当前格子，尝试放每一个元素
        repeat_string_recursive(src, dest, cur_str + src[i], cur+1, n);
    }
}

vector<string> repeat_string(vector<string> &src, int n) 
{
    vector<string> dest;
    repeat_string_recursive(src, dest, "", 0, n);
    return dest;
}

全排列问题
在上述问题中，我们可以在每个格子里面放相同的元素，那如果每个元素最多只能放一次，所以我们在需要再上述代码中修改一下，能够保证每个元素只能放入一次，增加一个数组visit[N], 如果A中的某个元素A[i]，在之前格子中出现过了，则A[i] = true, 否则为false。

vector<int> visit;
void repeat_string_recursive(vector<string> &src, vector<string> &dest, string cur_str, int cur, int n)
{
    if (cur == n) { //当cur = n时，则表示到达末尾，添加一个元素
        dest.push_back(cur_str);
        return ;
    }
    for (int i = 0; i < src.size(); i++) { // 在当前格子，尝试放每一个元素
    	if (visit[i]) // 如果visit[i]为1，则表明src[i]在之前的格子中出现，不能尝试了
    		continue; 
    	visit[i] = 1; // 打算放src[i]，这个元素，则visit[i]标记位1
        repeat_string_recursive(src, dest, cur_str + src[i], cur+1, n);
        visit[i] = 0; // src[i]尝试过了，回溯的时候，visit[i]要恢复原来的值，标记为0
    }
}

vector<string> repeat_string(vector<string> &src, int n) 
{
    vector<string> dest;
    visit.resize(src);
    repeat_string_recursive(src, dest, "", 0, n);
    return dest;
}

全排列问题，从n个不同元素中，取n个元素进行排列，因此是调用repeat_string(src, src.size())，即可实现；

C++全排列STL算法

1) bool next_permutation(vec.begin(), vec.end()); 求下一个排列组合，当存在下一个排列组合时，返回true, 否则false
2）bool prev_permutation(vec.begin(), vec.end()); 求上一个排列组合，当存在上一个排列组合时，返回true, 否则false

注意：使用之前需要进行排序，next使用升序，prev使用降序，否则只能找到当前序列之后的全排列

vector<string> vec = {"1", "2", "3"};
do {
    for (int i = 0; i < vec.size(); i++)
        cout << vec[i];
    cout << endl;
} while (next_permutation(vec.begin(), vec.end()));
//输出：
//123
//132
//213
//231
//312
//321