简单枚举枚举排列

时间: 2023-08-15 admin 互联网

简单枚举 / 枚举排列

简单枚举 / 枚举排列

 本文参考《算法竞赛入门经典》第七章《暴力枚举法》,提出的是暴力“列举”出所有可能性并一一试验的方法。

目录

1 简单枚举

2 枚举排列

2.1 生成1~n的排列

2.2 生成可重集的排列

2.3 解答树

2.4 下一个排列


一、简单枚举

简单枚举就是枚举一些例如整数、子串的简单类型。但是如果拿到题目直接上手枚举,可能会导致枚举次数过多(甚至引起TLE)。因此在枚举前先要进行分析。

比如例题 除法(Division,Uva 725)

对于这道题大多数人的思路是直接对abcde和fghij进行0~9的枚举,但是这样会导致枚举次数过多。所以可以从两个角度对解题思路进行优化。

第一点是抓住abcde/fghij=n的表达式。式子中的n由输入决定,abcde可以由枚举得来,那么fghij也就可以通过除法相应得来,不需要在进行一次枚举。也就是说原来确定了前五个数字,而fghij需要通过剩余5个数字的枚举排列结果和abcde一一相乘来确定结果;但是其实只需要根据算式求出此时成立条件下的fghij并判断是否合法即可。

那么第二点就是“合法”的判断。合法的条件是fghij中没有数字和abcde重合。在此之前首先判断abcde和除法得出的fghij位数之和是否等于10,可以节省大量比较的过程。如果两者位数相加超过10可以直接终止枚举。

所以看似简单的一道题加入枚举前分析后能节省大量的笔墨。

例题 最大乘积(Maximum Product,Uva 11059)

 该题主要思路是将“子串”二点枚举转换成“起点”和“终点”的枚举。此处还需要注意的是原题中要求每个元素绝对值不超过10且不超过18个元素,由于数据结果可能较大需要使用 long long 型存储。

例题 分数拆分(Fraction Again?!,Uva 10976)

 该题中枚举对象很显然是x和y,但是需要对他们框定一个范围,不然会一直向正无穷枚举过去。根据题目要求x≥y和1/k=1/x+1/y,根据不等式可以化成y≤2k,从而限定了枚举的范围。限定了y的范围从而可以通过等式求出x。

所以总结下来,简单枚举虽然简单,但是有三个注意点:

  • 枚举前先分析题目,尽量减少枚举对象(或具体化/可操作化)
  • 枚举范围可以通过数学计算框定
  • 枚举通常涉及大量数据的运算,注意存储数据的数据类型(有时int可能不够用)

二、枚举排列

枚举排列引入于“打印所有排列”的问题——根据输入的整数n,按照字典序排序输出前n个数的所有排列。(补充,两个序列的字典序大小关系=从头开始第一个不相同位置处的大小关系)

2.1 生成1~n的排列

可以使用递归的思想,一层层的递归思想和字典序“逐层比较”的思想较为契合。如果使用其他方法(比如循环),会发现这是个非常麻烦的过程,因为每一位的选择是相互嵌套叠加的,当你选定一位的数字还要面对后面诸多位的选择,而且每一位的选择原则是一样的——从没有出现过的数字中从小到大取,因此所以使用递归:

//n指排列总长度,A指存储当前排列的数组,cur指当前序列中已经有的元素个数
void print_permutation(int n,int *A,int cur)
{if(cur==n){   //已经完成整个串的递归“赋值”for(int i=0;i<n;i++)printf("%d",A[i]);printf("\n");}else{for(int i=1;i<=n;i++){  //尝试在A[cur]中填各种整数iint ok=1;           //判断这个数字是否之前出现过for(int j=0;j<cur;j++)if(A[j]==i) ok=0;   //如果已经在前面出现过,就不能选if(ok){A[cur]=i;       //填上一位数字print_permutation(n,A,cur+1);  //递归}}}
}

这里无需担心数组A会在函数中一次次被改变——因为递归是一个“深究到底”的进程,就像在树的DFS中一样,只有遍历完一条完整的枝条才会去下一小条。这里也是应用该特点,当执行到“叶子”(也就是本题中串已经完整赋值完成)就立刻输出,所以本次递归不会对下一次产生影响(即使数组中数据残余,递归中会将每一位数字重新检查后输出)。


2.2 生成可重集的排列

上面的代码由于有重复判断,所以只适用于无重复从0开始连续数的枚举排列。但是当需求改为“输入一个数组P,输出数组的字典序枚举排列”,如果只是将P从小到大排序、后将P加入到print_permutation参数列表中并改写A[j]=P[i]/A[cur]=P[cur],不能处理数组中元素重复的问题。

一个解决方法是统计A前序数组中该元素出现的次数,如果出现的次数小于原数组中的出现次数,那么还可以放入该数。但是这个方法有一个极大的安全隐患——如果仅输入111,将会输出27个111序列。因为这27个111中的1每次取得位置都不一样,可以画一张图来简单解释一下:

 也就是说,枚举的下标i不应该重复、不遗漏的取遍所有P[i]值,而恰好这里P数组已经经过排序,所以只需要选择P的第一个元素及所有“和前一个元素不同”的元素。可以用下图对应上图解释这个算法的作用:

 所以只要在算法中加一句判断即可:

if(!i||P[i]!=P[i-1])  //只有第一位或者与前一个元素不同的才能加入后一位

2.3 解答树

假设序列长度n,填充数字为1~n,当我们使用递归进行枚举排列时,一定能列出一个这样的树:

这棵树展示的是从虚无到整个递归完成的完整解题过程,所以称为解答树。和二叉树不同,它基本每一层的结点个数都不同:

层数每个结点的子节点个数该层结点个数
0(根节点)n1
1n-1n
2n-2n*(n-1)
..................
n无(都是叶子)n!

根据泰勒公式,可以求出该树的所有节点个数之和:

根据这个式子的极限,由于叶子节点和倒数第二层都是n!个结点,那么上面的各层加起来之和都达不到n!个结点。所以多数情况下解答树结点几乎全部来自于最后一两层。

2.4 下一个排列

枚举排列的方法除了递归枚举(以上所有的都是递归枚举),还能使用STL中的库函数next_permutation。该函数通过循环中不断调用实现“取下一个排列”的功能:

#include <cstdio>
#include <algorithm>   //该头文件包含了next_permutation
using namespace std;int main(){int n,p[10];scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&p[i]);sort(p,p+n);       //排序,得到p的最小序列do{for(int i=0;i<n;i++)printf("%d",p[i]);   //输出序列pprintf("\n");}while(next_permutation(p,p+n));   //求下一个序列return 0;
}

如果想要正确的使用next_permutation,第一次传入的必须是最小序列(经过sort(p)后),然后不断地循环,每一次执行后的p就是本次生成的排列。所以不需要另外开辟数组存放枚举排列。

通常使用do-while循环,因为最小序列由sort形成不需要调用函数。函数返回值为布尔值,如果已经生成完,该函数返回值为false,也可以自动结束函数。