全排列&子集的生成

全排列

生成 1 ~ n 的全排列

#include<stdio.h>
#define bool int
#define false 0
#define true 1
#define N 5
void dfs(int index,int *visit,int n,int *num){//index表示num的下角标
    if(index == n ){
        for (int i = 0; i<n; i++)  printf("%d ",num[i]);
        printf("\n");
        return ;
    }
    for(int i = 1 ; i <=n ; i ++){  //i 的范围大小 表示num的数字由哪些数字组成
        if(!visit[i]){//判断数字是否被用  判断的方法是根据visit的元素下角来看的若角标对应的值是1 则这个数字被使用 就判断下一数字
            visit[i] = true;//若没被使用  先标志记录下这个数字,
            num[index] = i;//把这个数字填到num对应角标去进去;
            dfs(index+1,visit,n,num);//下一位
            visit[i] = false;//将该数字使用完置为0
        }
    }
}

int main(){
    int num[100];
    bool visit[100];   //用来记录数字是否使用过
    dfs(0,visit,N,num);//递归存最后一位开始循环所有排列可能 ，逐位向前推进
    return 0;
}

输出：

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1 

断点打在这里

index == 0

index==1

数字被使用后会被记录，避免了重复以此类推

子集的生成

生成{1，2，3，.......n}的子集

• 位向量法
  构造一个位向量 have[i] .
  表示集合{0,1,3,4,6}

#include "stdio.h"
#define N 5
int have[N] = {0};
int num[N];
void f(int cur,int n){//cur表示位数
    if(cur == n){
        for (int i = 0; i <= cur; i++) {
            if(have[i]){
                printf("%d ",i);
            }
        }
        printf("\n");
        return;
    }
    have[cur] = 0;//不选cur个元素
    f(cur+1, n);
    have[cur] = 1;//选cur个元素
    f(cur+1, n);
}

int main(){
    f(1,N+1);
    return 0;

}

• 二进制法
  移位运算

#include<stdio.h>
void binary(int n, int s) {
    for(int i = 0; i < n; i++){
        if(s & ( 1<<i) ) //1左移i位，监测s的哪一位为1，同或为1的话输出
            printf("%d ", i+1);
    }
    printf("\n");
}
int main()   {
    int n = 2;
    for(int i = 0; i < (1<<n); i++){  //循环 2^n-1次 因为 1 左位移n次  相当于 循环2^n - 1
            binary(n, i);
    }
    return 0;  
}