全排列函数

什么是全排列？

简单来说就是排列组合的所有情况，并按照字典顺序输出
例如：123全排列的结果为

1
2
3
4
5
6
123
132
213
231
312
321

而实际上全排列需要在代码中用复杂的深度搜索来写
这实在是太复杂了！！！
于是我就发现了全排列函数这个东西^__^
现在我们就来学习一下这个高级函数————next_permutation

全排列函数

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>  
#include <algorithm>  
using namespace std;  
int main()  
{  
    int num[3]={1,2,3};  
    do  
    {  
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
    }while(next_permutation(num,num+3));  
    return 0;  
}

  • 全排列函数详细定义
    对于next_permutation函数，其函数原型为：

    #include

    bool next_permutation(iterator start,iterator end)

当当前序列不存在下一个排列时，函数返回false，否则返回true

  • 全排列函数的特性

next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。

另外，需要强调的是，next_permutation()在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。比如，如果数组num初始化为2,3,1，那么输出就变为了：

1
2
3
231
312
321

全排列函数的应用

题目链接

题目要求我们按要求完成5*5数独，且只要填ABC，可以有空格子
一种方法是遍历每一个格子，逐个填入，
时间复杂度(4^25)，显然不行
不过我的朋友使用了大量剪枝，最后还是过了
%%%大佬 qinye_leaf

代码链接

但是我们刚学了全排列函数，就不能使用一下吗？
你别说，还真能使用！
我们只要先填写每一行，然后就只用40^5就能计算完了
因为可以加上一个判断，看看每一行是否符合标准(也算剪枝吧)

1
2
3
4
5
6
7
8
9
10
11
12
vector<string> eachrow(int row) {
    vector<string> result;
    string h=string(n-3,'.')+"ABC";
    do{ for(int i=0;i<n;i++){
        if(h[i]!='.'){
            if(h[i]==r[row]) result.push_back(h);
            break;
        }
    }
    }while(next_permutation(h.begin(),h.end()));
    return result;
}

那么这样我们就能得到每一行的可能情况，每行40种
之后就可以正常的DFS了

个人AC代码链接