全排列算法总结
条评论全排列递归算法
算法思想
求 n 位的字符串的全排列,先确定第 0 位,然后对后面 n-1 位进行全排列,在对 n-1 为进行全排列时,先确定第 1 位,然后对后面的 n-2 位进行全排列…由此得到递归函数和递归的结束条件。全排列也就是交换位置,到 n-2 位时,就是将 n-2 和 n-1 交换位置。
例如输入字符串abc
,则打印出 a、b、c 所能排列出来的所有字符串 abc
、acb
、bac
、bca
、cab
和 cba
。具体过程如下:
- 第一位是 a 固定,对后面的 bc 交换位置得 abc,acb;
- 当 a 和 b 交换位置之后,得到 bac,对 ac 进行全排列 bac,bca;
- 当 a 和 c 交换位置之后,得到 cba,对 ba 进行全排列得cba,cab。
实现
于是我们根据这种思想写出第一个版本的算法:
1 | void perm(char *list, int i, int n){ |
这样我们实现基本的全排列的功能,但是这样我们并不能解决一种情况,即类似于abb
去重的问题,abb
这种交换后一样的情况在输出时会输出两个,于是我们需要对我们的算法进行改进,得到第二版的算法:
1 | bool isSwap(char *list, int begin, int end) { |
我们在进行交换前进行判断,当第 i 个字符和第 j 个字符交换位置时,判断范围是 [i, j) 是否有和 j 重复的数,如果重复我们跳过这种情况。
例题
题目内容:对字符串(数字,字母,符号)进行全排列,并统计全排列的种树
输入描述:输入一个字符串
输出描述:输出字符串的全排列,每种情况占一行,最后一行输出全排列的个数
输入样例
123
输出样例
123
132
213
231
312
321
6
这题目的坑在于对输出的全排列需要排序,ac代码如下:
1 |
|
使用next_permutation(排列组合)函数
使用
对于next_permutation函数,其函数原型为:
1 |
|
当当前序列不存在下一个排列时,函数返回 false,否则返回 true。
例如这个例子:
1 |
|
输出的结果为:
1 | 1 2 3 |
当把 while(next_permutation(num,num+3)) 中的 3 改为 2 时,输出就变为了:
1 | 1 2 3 |
由此可以看出,next_permutation(num,num+n) 函数是对数组 num 中的前 n 个元素进行全排列,同时并改变num数组的值。
另外,需要强调的是,next_permutation() 在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。比如,如果数组 num 初始化为 2,3,1,那么输出就变为了:
1 | 2 3 1 |
next_permutation() 函数功能是输出所有比当前排列大的排列,顺序是从小到大。
prev_permutation() 函数功能是输出所有比当前排列小的排列,顺序是从大到小。
此外,next_permutation(node, node+n, cmp) 可以对结构体 num 按照自定义的排序方式 cmp 进行排序。
举例
经典的24点
问题就可以用全排列来暴力解决,北邮复试机考就考到了这个题。
本文参考自:
- 本文链接:全排列算法总结
- 发布时间:2019年03月18日 - 19:16:30
- 更新时间:2021年02月03日 - 6:56:56
- 版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!
分享