(逆)康托展开
康托展开是一种全排列到自然数的映射,简而言之,康托展开就是一种计算某排列在全排列规则下的第几个。
( 什么是全排列?例如:一个数组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
更多推荐
(逆)康托展开
发布评论