遇到这个算法是在大牛写的10行的8皇后问题中，下面首先给出这个10行就解决了8皇后的NB代码，我目前还是没有看懂对于皇后不在同一列的判断，因为他巧妙的用了移位操作。
#include<iostream>
#include<algorithm>
#include<bitset>
#include<numeric>
#include<utility>
int main() {
int i = 0;
for (int queens[] = {0,1,2,3,4,5,6,7}; std::next_permutation(queens,queens+8);)
if ((std::bitset<15>(std::accumulate(queens,queens+8, std::make_pair(0, 0), [](std::pair<int, int> a, int b){return std::make_pair((1<<(b+a.second))|a.first,a.second+1);}).first).count() == 8) && (std::bitset<15>(std::accumulate(queens, queens+8, std::make_pair(0, 0), [](std::pair<int, int> a, int b){return std::make_pair((1<<(7+b-a.second))|a.first, a.second+1);}).first).count() == 8))
std::cout << ++i << " : " << queens[0] << queens[1] << queens[2] << queens[3] << queens[4] << queens[5] << queens[6] << queens[7] << std::endl;
return 0;
}
在上面的代码中，用next_permutation的原因是可以生成用0~7表示的所有序列。然后我们用if语句判断此时的序列(也就是每一个列序列)是否符合条件，要是符合就输出，否则就跳过，相当于用了打表的方式，列出所有可能的结果再寻找符合条件的。next_permutation的作用就是生成这所有的可能序列。
next_permutation的作用是：生成下一个较大的序列。perv_permutation的作用是生成下一个较小的序列。
以next_permutation举个例子：
我们用(a1 a2 … am)来表示m个数的一种序列。设序列pn=<3 6 4 2>，根据定义可算得下一个序列pn+1=<4 2 3 6>。观察pn可以发现，其子序列<6 4 2>已经为减序，那么这个子序列不可能通过交换元素位置得出更大的序列了，因此必须移动最高位3（即a1）的位置，且要在子序列<6 4 2>中找一个数来取代3的位置。子序列<6 4 2>中6和4都比3大，但6大于4。如果用6去替换3得到的序列一定会大于4替换3得到的序列，因此只能选4。将4和3的位置对调后形成排列<4 6 3 2>。对调后得到的子序列<6 3 2>仍保持减序，即这3个数能够生成的最大的一种序列。而4是第1次作为首位的，需要右边的子序列最小，因此4右边的子序列应为<2 3 6>，这样就得到了正确的一个序列pn+1=<4 2 3 6>。
下面我们用代码验证一下
#include<iostream>
#include<algorithm>
#include<vector>
using std::cout;
using std::cin;
using std::endl;
int main(int argc,char *argv[])
{
int chs[] = {3,6,4,2};
int count = sizeof(chs)/sizeof(*chs);
std::vector<int> vchs(chs,chs+count);
std::next_permutation(vchs.begin(),vchs.end());
for(auto u:vchs) cout << u << " ";cout << endl;
return 0;
}
下面看看它的实现
#include<iostream>
#include<algorithm>
#include<string>
using std::cout;
using std::cin;
using std::endl;
int main(int argc,char *argv[])
{
for(std::string str;cin >> str ;) {
//如果为空，直接结束
if(str.empty()) {
continue;
}
//长度小于等于一的没有子序列
if(str.length() <= 1) {
cout << "No " << endl;
}
std::string::iterator iPivot = str.end(),iNewHead;
//从最后往前找递减序列，直到找到
for(--iPivot;iPivot != str.begin();--iPivot) {
if(*(iPivot-1) <= *iPivot) {
break;
}
}
//如果一直找到开头，就说明此时已经是一个递减的序列，不会再有比它大的序列了
if(iPivot == str.begin()) {
cout << "No" << endl;
}
iPivot--;
//否则从右侧序列中找小于刚才的iPivot序列的
for(iNewHead = iPivot+1;iNewHead != str.end();++iNewHead) {
if(*iNewHead < *iPivot) {
break;
}
}
//然后交换它们的元素
std::iter_swap(iPivot,--iNewHead);
//然后将后面的翻转
std::reverse(iPivot+1,str.end());
cout << str << endl;
}
return 0;
}