STL全排列算法next_permutation和prev_permutation

浏览数：27 / 时间：2015年06月08日

全排列的问题取决于如何找到“下一个”，然后就用同样的方法找到全部的排列

全排列这个问题其实和我们数数：11,12,13,14,15,16,17,18,19,20,21，一样的规律，只不过他的变化只要那固定的几个数自每次都出现，这就导致我们传统的连续整数会在那里丢失一部分；你如何对剩下的这些全排列中的数字看成是“连续的”一列数字，对于“第一个”“最小的数字”找到它的“下一个”，然后用同样的方法找到再“下一个”，一直到“最后一个”，你就正好把全排列找到了。

下面只利用next_permutation从“第一个”开始，修改内容到“下一个”，知道所有的都遍历完，不再有”下一个“为止

#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<typename T>
void print(T begin,T end)
{
    while(begin != end)
    {
        cout<<*begin++<<" ";
    }
    cout<<endl;
};

void TestArray() 
{
    char chs[] = {'1', '2', '3', '4', '5'};
    int count = sizeof(chs)/sizeof(char);

    print(chs,chs+count);// print the first
    //next_permutation 会改变元素的内容，让其成为“下一个排列”，
    //返回值表示是否有下一个排列，排列按照全排列的升序进行。
    //与之对应的是prev_permutation()
    while(next_permutation(chs+0, chs + count))//print the next until there is no next
    {
        print(chs,chs+ count);
    }
}

int main(int argc, char *argv[])
{
    TestArray();

    return 0;
}

输出如下：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
请按任意键继续. . .