（逆）康托展开

（逆）康托展开

康托展开是一种全排列到自然数的映射，简而言之，康托展开就是一种计算某排列在全排列规则下的第几个。
（ 什么是全排列？例如：一个数组num[3]={1,2,3}，那么它的全排列就是1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1。
#include
#include
using namespace std;

int main()
{

int num[3]={1,2,3};
while(next_permutation(num,num+3)){for(int i=0;i<3;i++){printf("%d ",num[i]);}printf("\n");
}
return 0;

}

`
更多的解释：=aladdin）
康托展开的计算方法：
Σ(n-i)!*ai（n为元素个数，i为元素的序号，ai为第i个元素后比之小的个数）
例如：
比312小的排列有(3-1)!*2+(3-2)!*0+(3-3)!*0=4，即312 的康托展开值为4+1=5.
逆康托展开的计算方法：
将康托展开值变为序列的方法，具体过程如下：
用 4 / 2! = 2余0，说明 ,说明比首位小的数有2个，所以首位为3。
用 0 / 1! = 0余0，说明 ，说明在第二位之后没有小于第二位的数，所以第二位为1。
最后一位自然就是剩下的数2。
通过以上分析，所求排列组合为 312。

参考：=aladdin