第七章（一）暴力求解法

枚举排列：(递归枚举）

A.输入整数n，按字典序从小到大的顺序输出前n个数的所有排序

 1 //递归,n是n个数,a是数组，cur是当前
 2     public static void print_permutation(int n,int[]a,int cur) {
 3         if(n==cur) {
 4             for(int i=0;i<n;i++)
 5                 System.out.print(a[i]+" ");
 6             System.out.println();
 7         }
 8         else {
 9             for(int j=1;j<=n;j++) {
10             int flag=1;
11             for(int i=0;i<cur;i++) {
12                 if(a[i]==j)//已经出现过了
13                 {
14                     flag=0;break;
15                 }
16             }
17             if(flag==1) {
18                 a[cur]=j;
19                 print_permutation(n,a,cur+1);
20             }
21         }
22         }
23     }

三个注意点：

一是n==cur是输出得出口，而不是n-1==cur，因为第n-1次仍需要放第n-1个进去。

二是不要忘记加else,或者if里面加return。

三是因为a数组是一直利用的，所以已经确定的其实是qiancur-1个，不是所有的。

B.将整数变为某个集合，输入集合p[i]，按字典序从小到大的顺序输出该集合的所有排序

 1 //    输入集合p[i]，按字典序从小到大的顺序输出该集合的所有排序，p[i]为有序数组
 2     //递归,n是n个数,a是数组，cur是当前,p是输入集合
 3     public static void print_permutation(int n,int[]a,int cur,int[]p) {
 4         if(n==cur) {
 5             for(int i=0;i<n;i++)
 6                 System.out.print(a[i]+" ");
 7             System.out.println();
 8             return;
 9         }
10             for(int i=0;i<n;i++) {
11                 if(i==0||p[i]!=p[i-1]) {
12                 int c1=0,c2=0;
13                 for(int j=0;j<cur;j++) 
14                     if(a[j]==p[i])c1++;
15                 for(int j=0;j<n;j++) 
16                     if(p[j]==p[i])c2++;
17                 if(c1<c2) {
18                     a[cur]=p[i];
19                     print_permutation(n, a, cur+1, p);
20                 }
21             }
22             }
23     }

子集生成

给定一个集合，枚举所有可能得子集

1.增量构造法：每次向集合中增加一个值，因为有序所以不会重复（集合中的数递增，定序了！）

//得到小于=n的所有子集
    public static void print_subset(int n,int[]a,int cur) {
        for(int i=0;i<cur;i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        //向集合中添加一个值
        int start=cur==0?1:a[cur-1]+1;
        for(int i=start;i<=n;i++) {
            a[cur]=i;
            print_subset(n, a, cur+1);
        }
    }

2.位向量法：

//将b[i]中的元素选择添加或者不添加到数组中，添加n次
    public static void print_subset1(int n,int[] b,int cur) {
        if(n==cur) {
            for(int i=0;i<n;i++) {
                if(b[i]==1)System.out.print(i+" ");
            }
            System.out.println();
        return;
        }
        b[cur]=1;
        print_subset1(n, b, cur+1);
        b[cur]=0;
        print_subset1(n, b, cur+1);
    }

3.二进制法：用对应位上的1或0来表示有无（妙啊！）

n的子集有2ⁿ个

//二进制法
    public static void print_subset2(int n,int s) {
        for(int i=0;i<n;i++)
            if((s&(1<<i))!=0)//判断s的第i为上是不是1
                System.out.print((i+1)+" ");
        System.out.println();
    }
public static void main(String[] args) {
    int n=3;
    for(int i=0;i<(1<<n);i++) {//2^n个
        print_subset2(n, i);
    }

第七章 （一）暴力求解法

第七章（一）暴力求解法