全排列
生成 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;
}
