全排列
生成 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的下角標(biāo)
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的數(shù)字由哪些數(shù)字組成
if(!visit[i]){//判斷數(shù)字是否被用 判斷的方法是根據(jù)visit的元素下角來看的若角標(biāo)對應(yīng)的值是1 則這個(gè)數(shù)字被使用 就判斷下一數(shù)字
visit[i] = true;//若沒被使用 先標(biāo)志記錄下這個(gè)數(shù)字,
num[index] = i;//把這個(gè)數(shù)字填到num對應(yīng)角標(biāo)去進(jìn)去;
dfs(index+1,visit,n,num);//下一位
visit[i] = false;//將該數(shù)字使用完置為0
}
}
}
int main(){
int num[100];
bool visit[100]; //用來記錄數(shù)字是否使用過
dfs(0,visit,N,num);//遞歸存最后一位開始循環(huán)所有排列可能 岂丘，逐位向前推進(jìn)
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
斷點(diǎn)打在這里
index == 0
index==1
數(shù)字被使用后會(huì)被記錄陵究，避免了重復(fù)以此類推
子集的生成
生成{1，2奥帘，3铜邮，.......n}的子集
- 位向量法
構(gòu)造一個(gè)位向量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表示位數(shù)
if(cur == n){
for (int i = 0; i <= cur; i++) {
if(have[i]){
printf("%d ",i);
}
}
printf("\n");
return;
}
have[cur] = 0;//不選cur個(gè)元素
f(cur+1, n);
have[cur] = 1;//選cur個(gè)元素
f(cur+1, n);
}
int main(){
f(1,N+1);
return 0;
}
- 二進(jìn)制法
移位運(yùn)算
#include<stdio.h>
void binary(int n, int s) {
for(int i = 0; i < n; i++){
if(s & ( 1<<i) ) //1左移i位，監(jiān)測s的哪一位為1寨蹋，同或?yàn)?的話輸出
printf("%d ", i+1);
}
printf("\n");
}
int main() {
int n = 2;
for(int i = 0; i < (1<<n); i++){ //循環(huán) 2^n-1次 因?yàn)?1 左位移n次 相當(dāng)于 循環(huán)2^n - 1
binary(n, i);
}
return 0;
}
