暴力求解法

7.1 简单枚举

例题:除法(UVa 725)

输入正整数n,按从小到大的顺序输出所有形如abcdefghij=n的表达式,其中a~j恰好为数字0~9的一个排列(可以有前导0)

分析

没有必要枚举0~9的全排列,只需要枚举fghij就可以算出abcde,然后判断是否所有数数字都不相同即可。不仅程序简单,而且枚举量也从10!降低到小于一万。而且当abcdefghij加起来超过10位时可以终止枚举。
由此可见,即使采用暴力枚举,也是要认真分析问题的。

例题:最大乘积(UVa 11059)

输入n个元素组成的序列S,你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是正数,应输出0(表示无解)。

分析

连续子序列有两个要素:起点和终点,因此只需要枚举起点和终点即可。由于每个元素的绝对值不超过10并且不超过18个元素,所以最大可能的乘积不会超过1e18,可以用long long存储。

例题:分数拆分(UVa 10976)

输入正整数k,找到所有的正整数x>=y,使得1/k = 1/x + 1/y

分析

2k范围内枚举y,根据y算出x即可。

7.2 枚举排列

我们设想如何打印全排列?输入整数n,按照字典序从小到大输出前n个数的所有排列。前面讲过,两个序列的字典序大小关系等价于从头开始第一个不相同位置处的大小关系。

生成1~n的排列

分析问题

我们尝试用递归的思想解决这个问题:先输出1开头的排列,然后输出2开头的排列,一直到n开头的排列。
1开头的排列特点是:第一位是1,后面是2~9的排列。根据字典序的定义,这2~9的排列也必须按照字典序输出。这样的话,所设计的递归函数需要以下参数:

  1. 已经确定的前缀序列,以便输出
  2. 需要进行全排列的元素集合,以便依次选出第一个元素。 这样可以得到一个伪代码:
void print_permutation(序列A, 集合S){
    if(S为空) 输出序列A;
    else 按照从小到大的循序依次考虑S的每个元素v{
        print_permutation(在A的末尾填加v后得到的新序列, S-{v});
    }
}

暂时不用考虑序列A和集合S如何表示。理解一下上面的伪代码。递归边界是S为空的情形,此时A是一个完整的排列,直接输出即可。接下来按照从小到大的顺序考虑S中的每个元素,每次递归调用以A开头。
下面考虑程序实现。不难想到用数组表示序列A,而集合S不需要保存,因为可以由序列A 完全确定——A中没有出现的元素都可以选。C语言中的函数在接受数组参数时无法得知数组的元素个数,所以需要传一个已经填好的位置个数,或者当前需要确定的元素位置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++){
        int 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);
        }
    }
}

循环变量i是当前考察的A[cur]。为了检查元素i是否已经用过,上面的程序用到了一个标识变量ok,初始值为1,如果发现有某个A[j]==i则改为0。如果最终ok依然是1,说明i没有出现过,就把它添加到序列末尾后递归调用。

生成可重集的排列

如果把问题改成:输入数组P,并按字典序输出数组A各元素的所有全排列,则需要对上述程序进行修改——把P加到print_permutation的参数列表中,然后把代码中的if(A[j]==i)A[cur]=i分别改成if(a[j]==P[i])A[cur]=P[i]。这样,只要把P的所有元素按从小到大的顺序排序,然后调用rpint_permutatuion(n, P, A, 0)即可。
这个方法看上去不错,可惜有一个小问题:输入1 1 1之后,程序什么也不输出,原因在于这样禁止A数组中出现重复,而在P中本来就有重复元素时,就失效了。
一个解决方法是统计a[0]~A[cur-1]P[i]出现的次数c1,以及P数组中P[i]出现次数c2。只要c1<c2,就能递归调用。

else for(int i =0; i < n; i++){
    int c1= 0; c2 =0;
    for(int j = 0; j < cur; j++) if(A[j] == P[i]) c1++;
    for(int j = 0; j < n; j++) if(P[i] == P[j]) c2++;
    if(c1 < c2){
        A[cur] = P[i];
        print_permutation(n, P, A, cur+1);
    }
}

这样的结果,输入1 1 1,输出了27个1 1 1。没有了遗漏,但是出现了重复。我们枚举的下标i应不重复,不遗漏地取遍所有P[i]值。由于P数组已经排过序,所以只需要检查P的第一个元素和所有的“与前一个元素不同”的元素。即只需要在i循环后加上if(!i || P[i] != P[i-1])即可。

解答树

下一个排列

枚举所有排列的另一个方法是从字典序最小排列开始,不停调用“求下一个序列”的过程。如何求下一个排列?C++的STL提供了next_permutation函数。

#include<cstdio>
#include<algorighm>
using namespace std;
int main(){
    int n, p[10];
    scanf("%d", &n);
    for(int i = 0; in; i++) scanf("%d", &p[i]);
    sort(p, p+n);
    do{
        for(int i = 0; i<n; i++) printf("%d", p[i]);
        printf("\n");
    } while(next_permuutation(p, p+n));
    return 0;
}

此方法同样适用于可重集。

7.3 子集生成

子集生成算法:给定一个集合,枚举可能的子集。

增量构造法

思路和代码

每次选出一个元素放到集合当中。

void print_subset(int n, int* A, int cur){
    for(int i = 0; i< cur; i++) printf("%d ", A[i]);
    printf("\n");
    int s = cur ? A[cur-1]+1 : 0;
    for(int i = s; i < n; i++) {
        A[cur] = i;
        print_subset(n, A, cur+1);
    }
}

和前面不同的是,A中的元素个数是不确定的,所以每次递归调用都要输出当前的集合。另外,递归边界也不需要显示确定——如果无法再继续添加元素,自然就不会再递归了。
上面的代码中用到了定序的技巧:规定A中的所有元素编号从小到大排列,就不会把同一个集合多次输出了。
在枚举子集的增量法中,需要用定序的技巧来避免同一个集合枚举两次。
这棵解答树上有2<<10个结点。因为每一个可能的A都对应着一个结点。而n元素的集合有2<<n个子集。

位向量法

思路和代码

构造一个位向量B[i],其中B[i]=1,当且仅当i在子集A中。

void print_subset(int n, int* B, int cur){
    if(cur == n){
        for(int i = 0; i < cur; i++)
            if(B[i]) printf("%d ", i);
        printf("\n");
        return;        
    }
    B[cur] = 1;
    print_subset(n, B, cur+1);
    B[cur] = 0;
    print_subset(n, B, cur+1);
}

必须当“所有元素是否选择”全部确定完毕之后才是一个完整的子集,因此仍然像以前那样当if(cur==n)成立时才输出。现在的解答树上有2047个结点,比刚才的方法略多。这个也不难理解:所有部分解(不完整的解)也对应着解答树上的结点。
在枚举子集的位向量法中,解答树的节点略多,但是在多数情况下依然够快。

二进制法

思路和代码

另外,还可以用二进制来表示子集:从左到右第i位(编号从0开始)表示元素i是否在集合S中。此时单单表示出集合是不够的,还需要对集合进行操作。幸运的是,常见的集合运算都可以用位运算符简单实现。最常见的二元位运算是&|^,他们和对应的逻辑运算非常相似。

void print_subset(int n, int s){
    for(int i =0; i < n;i++)
        if(s&(1<<i)) printf("%d ", i);
    printf("\n");
}

要枚举子集也很简单:

for(int i = 0; i < (1<<n); i++)
    print_subset(n, i);

从代码量来看,二进制法是最简单的方法。