康托展开【Template】

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<cmath> #include<map> #include<set> #include<queue> using namespace std; #define ll long long int char a[200] = { '1','5','3','2','4' }, s[200]; int num[200]; int fac[] = { 1,1,2,6,24,120,720,5040,40320 };//jiecheng int kangtuo(int n, char a[]) {//已知数字求位置 int i, j, t, sum; sum = 0; for (i = 0; i < n; i++) { t = 0; for (j = i + 1; j < n; j++) { if (a[i] > a[j]) ++t; } sum += t * fac[n - i - 1]; } return sum + 1; } void reverse_kangtuo(int n, int k, char s[])//已知位置求数字 { //1~n的全排列，其中的第K个数为s[] int i, j, t, vst[8] = { 0 }; --k; for (i = 0; i < n; i++) { t = k / fac[n - i - 1]; for (j = 1; j <= n; j++) { if (!vst[j]) { if (!t) break; --t; } } s[i] = '0' + j; vst[j] = 1; k %= fac[n - i - 1]; } } int main() { int tmp = kangtuo(5, a); cout << tmp << endl; reverse_kangtuo(5, 5, s); for (int i = 0; i <= 10; i++) { cout << s[i]; } cout << endl; system("pause"); return 0; }