###利用康托展开求第K个全排列
-
利用康托编码的思路，假设有 n 个不重复的元素，第 k 个排列是 a1,a2,a3,...,an
-
那么我们把 a1 去掉，那么剩下的排列为 a2,a3,...,an,共计 n−1 个元素，n−1 个元素共有 (n−1)! 个排列
-
于是就可以知道
a1 = k/(n−1)! k2 = k%(n−1)! a2 = k2/(n−2)! ... = ... kn−1 = kn−2%2! an−1 = kn−1/1! an = 0
###Code
#include <iostream>
#include <string>
using namespace std;
long long factorial(int n){
if(1 == n || 0 == n){
return 1;
}
int ret = 1;
for(int i = 1; i <= n; ++i){
ret *= i;
}
return ret;
}
string kth_permutation(string str, int k){
int n = str.size();
string s = str;
string ret;
int base = factorial(n - 1);
//cantor begins at 0
k--;
for(int i = n - 1; i > 0;){
auto pos = next(s.begin(),k / base);
ret.push_back(*pos);
s.erase(pos);
k %= base;
base /= i--;
}
ret.push_back(s[0]);
return ret;
}
int main()
{
string test = "123";
for(int i = 1; i <= factorial(test.size()); ++i){
cout<<kth_permutation(test,i)<<endl;
}
system("pause");
return 0;
}###Testing
