简单枚举法

简单枚举法

1 在阅读之前

前备知识可阅读递归

1 介绍

1.1 简单枚举

在进行归纳推理时,如果逐个考察了某类事件的所有可能情况,因而得出一般结论,那么这结论是可靠的,这种归纳方法叫做枚举法。枚举法是利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检验,从中找出符合要求的答案,因此枚举法是通过牺牲时间来换取答案的全面性。效率不高,但是正确性是绝对的。

采用枚举算法解题的基本思路:

  1. 确定枚举对象、枚举范围和判定条件。
  2. 枚举可能的解,验证是否是问题的解。

1.2 例题

  • 问题:输入正整数$n(2 \leq n \leq 79)$,按从小到大的顺序输出所有形如$abcde/fghij=n$的表达式,其中$a$-$j$恰好为数字$0$-$9$的一个排列(可以有前导0)。(《算法竞赛入门经典》P182

原题

枚举0-9的所有排列吗?没这个必要。只需要枚举fghij就可以算出abcde,然后判断是否所有数字都不相同即可。不仅程序简单,而且枚举量也从10!=3628800降低至不到1万,而且当abcde和fghij加起来超过10位时可以终止枚举。由此可见,即使是使用暴力枚举,也要认真分析问题来优化的。

这道题是比较容易想出判定条件的枚举。下面介绍稍微难一些的简单枚举:枚举排列枚举子集

2 枚举排列

2.1 生成1-n的排列

生成排列的一个最基本的做法就是递归。我们从序列中一个一个的来挑取元素就可以了。请看代码。

  • 例2.1.1
void print_permutation(int n,int cur)
{
    if (cur==n)    //输出
    {
	    for (int i=0;i<n;i++) printf("%d",A[i]);
	    puts("");
    }
    else for (int i=1;i<=n;i++)    //填1-n
    {
        int ok=1;
        for (int j=0;j<cur;j++)
            if (A[j]==i) ok=0;
        if (ok) {A[cur]=i; print_permutation(n,cur+1);}
    }
}

2.2 生成可重集的排列

给定一个数组P,要求按照数组序(元素在数组中出现的顺序)输出数组P全元素的全排列。由于数组P内的元素是可以重复的,我们在枚举时需要注意。请看代码。

  • 例2.2.1
void print_permutation(int n,int cur)
{
    if (cur==n)    //输出
    {
        for (int i=0;i<n;i++) printf("%d",A[i]);
        puts("");
    }
    else for (int i=0;i<n;i++)    //填1-n
        if (!i||P[i]!=P[i-1])
        {
            int c1=0,c2=0;
            for (int j=0;j<cur;j++) if (A[j]==P[i]) c1++;
            for (int j=0;j<cur;j++)
                if (A[j]==i) ok=0;
            if (c1<c2) {A[cur]=P[i]; print_permutation(n,cur+1);}
        }
}

这种枚举排列的算法如果要按字典序从小到大输出排列的话,需要先将数组P排个序。

2.3 时间复杂度与解答树

假设给定的数组为P[1,2,3],那么用树来表示就是:

这棵树与二叉树是不同的。从上往下数,第一层()结点有1个结点,第二层有3个结点,第三层有6个结点,第四层有6个结点。第四层的结点都没有子结点,且每个结点都对应一个排列,一共是3!=6个节点。这棵树被称为“解答树”。

  • 解答树:如果某问题的解可以由多个步骤得到,而每个步骤都有若干种选择(这些候选方案集可能会依赖于先前作出的选择),且可以用递归枚举法实现,则它的工作方式可以用解答树来描述。

由解答树我们可以计算出枚举排列算法的复杂度。我们需要计算解答树的总结点数。有兴趣可以推一下,为了减少篇幅就不介绍计算过程。最终得到的式子是:

$$ T(n)=n!\sum_{k=0}^{n-1}\frac{1}{k!} $$

而:

$$ \lim_{x \rightarrow \infty}\sum_{k=0}^{n-1}\frac{1}{k!}=e $$

所以$T(n)=n!e$,枚举排列算法的时间复杂度为$O(n!)$。

2.4 C++STL next_permutation

枚举排列的另一种方法就是从字典序最小排列开始,不停调用“求下一个排列”的过程。如何求下一个排列呢?C++STL有一个函数next_permutation能完成这个任务,它在Alogrithm库中。如何使用?请看代码。

next_permutation(p,p+n);

可以看出用法是这样的:next_permutation(排列起始地址,排列结束地址的后一个地址),你也可以想象成是一个左闭右开区间。还有,当存一下个排列时,函数返回1,当不存在下一个排列时,函数返回0。这可以作为循环终止的条件。

3 枚举子集(真集合)

3.1 增量构造法

枚举子集的第一种方法就是一个一个放元素到集合中。为了简单起见,集合装的是0-n-1的数字。请看代码。

  • 例3.1.1
void print_subset(int n,int cur)
{
    for (int i=0;i<cur;i++)
        printf("%d",Set[i]);    //打印当前集合
    puts("");
    int s=cur?A[cur-1]+1:0;    //使得集合里面的元素是升序的
    for (int i=s;i<n;i++)
    {
        Set[cur]=i;
        print_subset(n,cur+1);
    }
}

和排列不同,因为子集的元素个数是小于等于原集合的元素个数的,所以在每次递归调用中都要输出当前集合。而且不需要添加边界条件,因为当cur>=n时,便会因为无法再加值到集合中而一层一层的退出递归。

时间复杂度怎样?这棵解答树上有1024个结点。不难理解,每次输出的都是子集,而子集个数有$2^n$个。

3.2 位向量法

第二种方法是构造一个位向量数组vec,而不是直接构造子集本身,其中vec[i]=1表示i在子集Set中,反之不在。为了简单起见,集合装的是0-n-1的数字。代码如下。

  • 例3.2.1
void print_subset(int n,int cur)
{
    if (cur==n)
    {
        for (int i=0;i<cur;i++)
            if (vec[i]) printf("%d ",i);
        puts("");
        return;
    }
    vec[cur]=1;    \\选第cur个元素
    print_subset(n,cur+1);
    vec[cur]=0;    \\不选第cur个元素
    print_subset(n,cur+1);
}

可以很明显的看出这很像数学课上老师讲解求集合的子集数那样:选还是不选第i个元素,每个元素有两种选择(选或者不选),有多少个元素就多少个2相乘。

这个的时间复杂度又是怎样的?这棵解答树上有2047个结点,比第一种方法要多,这是因为不完整的解也在解答树的结点上。如果要计算的话就是:

虽然时间要慢点,但是这仍为效率不错的算法。

3.3 二进制法

最后一种方法是用二进制。为了简单起见,集合装的是0-n-1的数字。请看表格

最后得出的子集是[5,3,2,0]。这就是二进制法的机制。可以知道,A&B,A|B,A^B可以分别对应集合的交,并和对称差。其次,空集为0,全集为(1<<n)-1。最后集合A的补集就为全集^A。知道这些以后,就可以写出代码了,代码如下。

  • 例3.3.1
void print_subset(int n,int s)
{
    for (int i=0;i<n;i++)
        if (s&(1<<i)) printf("%d ",i);    //该位为1
    printf("\n");
}

int main()
{
    for (int i=0;i<(1<<n);i++)    //0为空集,这条循环遍历所有子集
	print_subset(n,i);
}

从代码量来看,二进制法是枚举子集最容易的方法。

4 枚举子集(假集合)

上一章节枚举的原集合都是真集合,即集合里的元素不会重复,那如果扩大一下范围,枚举假集合(即元素会重复)的子集,或者说枚举子序列应该怎么做呢?

答案是我们可以将上一章节中的1-n-1的数都对应一个值。这样,不仅可以枚举所有形式的真集合的子集,假集合的子集也可以被枚举了,并且我们只需要在原本的代码上修改很小的一段就可以完成了。代码如下。

  • 例4.1
int Set[maxn];
void print_subset(int n,int s)
{
    for (int i=0;i<n;i++)
        if (s&(1<<i)) printf("%d ",Set[i]);    //该位为1
    printf("\n");
}

int main()
{
    for (int i=0;i<(1<<n);i++)    //0为空集,这条循环遍历所有子集
        print_subset(n,i);
}

这是二进制做法,其他做法的修改也很简单,就不描述了。


文章内容摘抄自 《算法竞赛入门经典(第二版)》

感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。