DFS实现全排列 algorithm

先举个例子，得到123的全排列：我们可以先让1分别和2,3交换（得到213,321），这样就确定了第一位的三种情况（123,213,321）。然后再对每种情况的剩下部分继续进行全排列。如123，从第二位开始，让2分别和后面的交换（得到132），这样就确定了第一位是1时第二位的两种情况（123,132）。第一位为2,3同理，这样共得到3*2=6种情况。
代码实现

void print(int l,int r){ for(int i=l; i<=r; i++) printf("%d ",a[i]); printf("\n"); } void dfs(int l,int r){if(l==r){//已经是最后一位 print(1,r); return; } for(int i=l; i<=r; i++){//确定第l位的r+1-l种情况 swap(a[l],a[i]); dfs(l+1,r); //交换后再确定第l+1位,直到最后一位 swap(a[l],a[i]); } }

此外C++ STL库中也有全排列的函数next_permutation
相关题目：第七届蓝桥杯C++B组省赛第3题
凑算式
BDEF
A + --- + ------- = 10
CGHI

这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。

解题思路：
遍历求解 ,全排列
通分之后
BD*100+E*10+F
A + --- + ---------------- = 10
CG*100+H*10+I

A*C*GHI+B*GHI+C*DEF=10*C*GHI

#include using namespace std; const int N=10; //a b c d e f g h i int a[N]={0,1,2,3,4,5,6,7,8,9}; int ans=0; void print(int l,int r){ for(int i=l; i<=r; i++) printf("%d ",a[i]); printf("\n"); } void dfs(int l,int r){ if(l==r){ //print(1,r); int def=a[4]*100+a[5]*10+a[6]; int ghi=a[7]*100+a[8]*10+a[9]; if((a[1]*a[3]*ghi)+(a[2]*ghi)+(a[3]*def)==10*a[3]*ghi){ //print(1,r); ans++; printf("%d+%d/%d+%d%d%d/%d%d%d=10\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]); } return; } for(int i=l; i<=r; i++){ swap(a[l],a[i]); dfs(l+1,r); swap(a[l],a[i]); } } int main(){ ans=0; dfs(1,9); printf("%d\n",ans); return 0; }

使用next_permutation函数

#include #include using namespace std; int main(){ //a,b,c,d,e,f,g,h,i int a[10]={1,2,3,4,5,6,7,8,9},count=0; do{ int ghi=(a[6]*100+a[7]*10+a[8]); int def=a[3]*100+a[4]*10+a[5]; if((a[0]*a[2]*ghi)+(a[1]*ghi)+(def*a[2])==10*a[2]*ghi){ count++; printf("%d+%d/%d+%d%d%d/%d%d%d=10\n",a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]); } }while(next_permutation(a,a+9)); printf("cout:%d\n",count); return 0; }

【DFS实现全排列】