算法分析--生成排列

排列简介

• 全排列，有顺序要求。
• 递归实现

如何实现

• 查找第u位置有哪些数字可以用，选择查到的第一个，填上去。

if(u > n){for(int i=1;i<=n;i++)cout<<path[i]<<" ";cout<<endl;
}

• 再去填写下一个数字。
• 什么时候不再填写，也就是递归终止了呢？要填写的位置 u >n的时候

for(int i=1;i<=n;i++){if(!state[i]){   // 查找还没用过的数字path[u]=i; // 填上去state[i]=1; dfs(u+1); // 去填写下一个数子state[i]=0; // 撤销我刚刚的选择，在这里填查到的第二个数字，第三个，第四个...}
}

综合代码

#include<iostream>
using namespace std;
int n;
int path[10];
int state[10];
void dfs(int u){if(u>n){for(int i=1;i<=n;i++)cout<<path[i]<<" ";cout<<endl;}for(int i=1;i<=n;i++){if(!state[i]){path[u]=i;state[i]=1;dfs(u+1);state[i]=0;}}
}
int main(){cin>>n;dfs(1);return 0;
}