c++ 算法 next_permutation

遇到这个算法是在大牛写的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;

}

巴特西

c++ 算法 next_permutation

最新文章

热门文章