排列数

问题描述 　　0、1、2三个数字的全排列有六种，按照字母序排列如下： 　　012、021、102、120、201、210 　　输入一个数n 　　求0~9十个数的全排列中的第n个（第1个为0123456789）。 输入格式 　　一行，包含一个整数n 输出格式 　　一行，包含一组10个数字的全排列 样例输入 1 样例输出 0123456789 数据规模和约定

　　0 < n <= 10!

1.先走到第一个位置，此时放置一个当前可以放置的数字当中最小的那个数字。 2.在走到第二个位置，放置一个当前可以放置的数字当中最小的那个数字。 … 3.到第10个位置时候，所有的数字已经放置完毕，属于第一个全排列。 4.收回第10个位置上的数字，此时还是只可以放置9，那么再到第9个位置面前，收回位置上的数字。 5.在第9个位置处，我们此时可以放置的数字有9，那么第10个位置放8.属于第二个全排列。 6.收回第10、9、8位置的数字，此时可以在第8个位置放置8. …

用一个数组标记当前的数字是否已经被使用过了。 int visited[11]; //一开始的时候没有被使用，初始化值为0.使用过了之后标记为1. int tmp[11]; // 表示这10个需要放置数字的位置。 深度优先搜索：

#include <iostream> using namespace std; int n,k=0; int visited[11]={0}; int tmp[11]; void dfs(int t) { if(t>=10) { k++; if(k==n) { for(int i=0;i<10;i++) cout<<tmp[i]; cout<<endl; return; } } else for(int i=0;i<10;i++) { if(!visited[i]) { tmp[t]=i; visited[i]=1; dfs(t+1); visited[i]=0; } } } int main() { cin>>n; dfs(0); return 0; }

若果用algorithm里自带的库函数会更简单，next_permutation(start,end)获取字符串的下一个全排列序列，字符串可以是string类型，那么start和end处分别传入首位迭代器

也可以是char*类型，那么start和end处传入首尾地址

#include<iostream> #include<algorithm> using namespace std; int main() { string s="0123456789"; int t; cin>>t; while((--t)>0&&next_permutation(s.begin(),s.end())); cout<<s<<endl; return 0; }