关于全排列的一些算法
关于全排列的一些算法
首先我有三个关于全排列的问题：
1.求全排列中，某一种排列的下一个
2.求全排列中，某一种排列是第几个
3.求全排列中，第n种排列是怎样的
当然，我所说的全排列是按照字典序所排列的
假如我们所要全排列的数码为1~9。
第一问：
求全排列中，某一种排列的下一个
这个问题关乎到一点点数论
先举个核桃：
1 2 3 4 5 6 7 8 9 的下一个
显然，按照字典序是
1 2 3 4 5 6 7 9 8
9 8 7 6 5 4 3 2 1 没有下一个了
所以我们能感受到，求下一个，与整个摆列的大小有关系，而且是越来越大。也就是说，我们只要找到合适的数字，做位置交换就可以了。
1 5 3 4 5 2 7 9 8
这个排列，我们首先从后往前找，找到一个数值下降：
8->9上升 9->7下降 再从右往左找比它大的最小的数字，显然是8
交换---> 1 5 3 4 5 2 8 9 7 这个时候，只是将第一个能换的数字变大了，但是按照字典序，后面的数字都要变小，所以后面要重新排列---> 1 5 3 4 5 2 8 7 9
结束了 代码是这样的：```
include<iostream>
using namespace std;
int a[10],k = 9,i,j,p; int main(){ for(i = 1;i<=9;i++) cin>>a[i]; while(a[k]<a[k-1]) k--; if(k == 1){ cout<<"No!"; return 0; } for(j = k;j<=9;j++){ int m = 100; if(a[j]>a[k-1]){ if(a[j]<m){ m = a[j]; p = j; } } } swap(a[p],a[k-1]); for(int l = k,r = 9;l<r;l++,r--) swap(a[l],a[r]); //这里的排序其实就是冒泡 for(i = 1;i<=9;i++) cout<<a[i]<<' '; return 0; }