Algorithm

Brute Force

Posted on 2018-11-16

枚举排列

输入整数n, 按照字典序从小到大的顺序输出前n个数的所有排列。

生成1~n的排列

尝试用递归的思想，先输出所有以1开头的(递归调用)，然后输出以2开头的…最后才是以n开头的排列。

递归函数需要的参数

  • 已经确定的”前缀”序列，以便输出

  • 需要进行全排列的元素集合，以便依次选做第一个元素

  • 伪码:

    1
    2
    3
    4
    5
    6
    7
    8
    void print_permutation(prefix A, 集合S){
      if(S为空) 输出序列A;
      else{
        按照从小到大的顺序依次考虑S的每个元素v{
          print_permutation(A+v, S-{v});
        }
      }
    }

  • C++
    不难想到可以用数组表示序列A, 而集合S根本不用保存，因为可以由序列A完全确定(A中没有出现的元素都可以选).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //n表示前缀长度(C++数组无法预知长度)
    void print_permutation(int n, int* A, int cur){
      if(cur == n){//if(S为空) 输出序列A;
        Print(A);
        return;
      }
      else for(int i=1; i<=n; i++){//尝试在A[cur]中填各种整数i
        int ok = 1;
        for(int j=0; j<cur; j++) if(A[j] == i) ok=0; //如果i已经在A中出现，不能再选
        if(ok){
          A[cur] = i;
          print_permutation(n, A, cur+1);
        }
      }
    }

生成可重集的排列

把问题改成，输入数组P, 并按照字典序输出数组A各元素的所有全排列，则需要对上述程序进行修改, 把P加到print_permutaion的参数列表中, 然后把代码中的if(A[j] == i) 和A[cur] = i分别改成if(A[j] == P[i])和A[cur] = P[i]. 这样，只要把P中的元素按从小到大的顺序排序，然后调用print_permutation(n, P, A, 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//n表示前缀长度(C++数组无法预知长度)
void print_permutation(int n, int* P, int* A, int cur){
  if(cur == n){//if(S为空) 输出序列A;
    Print(A);
    return;
  }
  else for(int i=1; i<=n; i++){//尝试在A[cur]中填各种整数i
    int ok = 1;
    for(int j=0; j<cur; j++) if(A[j] == P[i]) ok=0; //如果i已经在A中出现，不能再选
    if(ok){
      A[cur] = P[i];
      print_permutation(n, A, cur+1);
    }
  }
}

但是有问题，输入1111后，程序什么也不输出（正确答案应该是唯一的全排列1111）.原因在于，这样 禁止A数组中 出现重复，而在P中本来就有重复元素时，这个禁令是错误的。

一个解决方法是，统计A[0] ~ A[cur-1]中P[i]出现的次数以及P[i]的出现次数c2. 只要c1<c2, 就能递归调用。

1
2
3
4
5
6
7
8
9
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_permutaion(n, P, A, cur+1);
  }
}

但是输入111，输出了27个111， 遗漏没有了，但是出现了重复: 先试着把第1个1个1作为开头，递归调用结束后再尝试用第2个1作为开头，递归调用结束后再尝试用第3个1作为开头，再一次递归调用。可实际上这3个1是相同的，应只递归一次而不是三次。

我们枚举的下标i应不重复，不遗漏地取遍所有P[i]值。由于数组P已经排过序，所以只需检查P的第一个元素和所有“与前一个元素不相同的元素。

1
2
3
4
5
6
7
8
9
10
11
else for(int i=0; i<n; i++){
  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<n; j++) if(P[i] == P[j]) c2++;
    if(c1<c2){
      A[cur] = P[i];
      print_permutaion(n, P, A, cur+1);
    }
  }
}

解答树

假设n=4, 序列为{1,2,3,4}. 下图所示的树显示除了递归函数的调用过程。其中结点内部的序列表示A
(*,*,*,*)

(1,*,*,*) (2,*,*,*) (3,*,*,*) (4,*,*,*)

(1,2,*,*) (1,3,*,*) (1,4,*,*) (1,5,*,*), ….

第0层有n个结点，第一层结点个有n-1个子结点， 共有n!个叶子。

所有的结点数目:

因此，在多数情况下，解答树的全部结点几乎全部来源于最后1，2层。

下一个排列

//todo:

子集生成

给定一个集合，枚举所有可能的子集。为了简单起见，本节讨论的集合中没有重复元素。

增量构造法

规定A中所有元素由小到大排列，避免{1,2}重复输出{1,2},{2,1}. 一次选出一个元素放到集合中。

1
2
3
4
5
6
7
8
void print_subset(int n, int* A, int cur){
  for(int i=0; i<cur; i++) print(A[i]);//打印当前集合
  int s = cur? A[cur-1]+1:0;//cur == 0, s = 0; cur!=0, s=A[cur-1]+1;确定当前元素的最小可能值
  for(int i=s; i<n; i++){
    A[cur] = i;
    print_subset(n, A, cur+1);
  }
}

位向量法

第二种思路是构造一个位向量B[i],而不是直接构造子集A本身, 其中B[i] = 1, 当且仅当i在子集A中。

必须当“所有元素是否选择”全部确定完毕后才是一个完整的子集，因此依然像以前那样，当if(cur == n)成立时才输出。有2^n种，解答树的结点变多。

1
2
3
4
5
6
7
8
9
10
11
void print_subset(int n, int* B, int cur){
  if(cur == n){
    for(int i=0; i<cur; i++){
      if(B[i]) print(i);//B[i] == 1
    }
  }
  B[cur] = 1;
  print_subset(n, B, cur+1);
  B[cur] = 0;
  print_subset(n, B, cur+1);
}

二进制法

可以用二进制来表示{0, 1,2,…, n-1}的子集S: 比如0011表示{2,3}在集合中。
全集: ALL_BITS = (1<<n)-1, A的补集ALL_BITS^A.

1
2
3
4
5
6
7
8
9
10
11
12
13
//输出S
void pirnt_subset(int n, int s){//打印{0, 1,2,..., n-1}的子集S
  for(int i=0; i<n; i++){
    if(s&(1<<i)) print(i);
  }
}

//枚举子集
void main(){
  for(int i=0; i<(1<<n); i++){
    pirnt_subset(n, i);
  }
}