康托展开简介_康托展开个人资料_康托展开微博_百科网
A-A+

康托展开简介_康托展开个人资料_康托展开微博

2017-12-15 06:04:33 科学百科 阅读 12 次

康托展开的公式/康托展开 编辑

  把一个整数X展开成如下形式:
  X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!
  其中,a为整数,并且0<=a[i] <=i<=n)

康托展开的应用实例/康托展开 编辑

  {1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个。123 132 213 231 312 321 。
  代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。
  他们间的对应关系可由康托展开来找到。
  如我想知道321是{1,2,3}中第几个大的数可以这样考虑 :
  第一位是3,当第一位的数小于3时,那排列数小于321 如 123、 213 ,小于3的数有1、2 。所以有2*2!个。再看小于第二位2的:小于2的数只有一个就是1 ,所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个。所以321是第6个大的数。 2*2!+1*1!+1*0!就是康托展开。
  再举个例子:1324是{1,2,3,4}排列数中第几个大的数:第一位是1小于1的数没有,是0个 0*3! 第二位是3小于3的数有1和2,但1已经在第一位了,所以只有一个数2 1*2! 。第三位是2小于2的数是1,但1在第一位,所以有0个数 0*1! ,所以比1324小的排列有0*3!+1*2!+0*1!=2个,1324是第三个大数。

康托展开的代码实现/康托展开 编辑

  后文的PASCAL程序经检验可以正确工作,并指示出了一个简洁的计算方法,和前文的运算思路略有不同,不需要检验某数码是否使用过,只需检查第(n+1-i)位之后比第(n+1-i)位小的位的数量,将这个数量作为公式中的a[i]。(1<=i<=n)
  并附此算法C++版本。

康托展开的代码(C++语言)

   const int PermSize = 12;
   long long factory[PermSize] = { 0, 1, 2, 6, 24, 120,720, 5040, 40320, 362880, 3628800,39916800 };
   long long Cantor(stringbuf) {
   int i, j, counted;
   long long result = 0;
   for (i = 0; i < PermSize; ++i) {
  counted = 0;
   for(j = i + 1; j < PermSize; ++j)
   if(buf[i] > buf[j])
  ++counted;
  result = result + counted *factory[PermSize - i - 1];
  }
   return result;
  }

康托展开的代码(Pascal语言)

  s为数组,用来存储要求的数,形如(1,3,2,4)。
  n为 数组中元素个数。
  fac[x]为x!
  *function cantor:longint:;
  *var
  * i,j,temp:integer;
  * num:longint;
  *begin
  * num:=0;
  * for i:=1 to n-1 do
  * begin
  * temp:=0;
  * for j:=i+1 to n do
  * if s[j]
  * num:=num+fac[n-i]*temp;
  * end;
  *cantor:=num+1;
  *end;

康托展开的代码(C语言)

  //参数int s[]为待展开之数的各位数字,如需展开2134,则s[4]={2,1,3,4}.long int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶层表 
  long cantor(int s[],int n)
  {
  long int i,j,temp,num;
  num=0;
  for(i=0;i
  temp=0;
  for(int j=i+1;j
  if (s[j]
  }
  num+=fac[n-i-1]*temp;//(或num=num+fac[n-i-1]*temp;)
  }
  return (num+1);
  }

康托展开的逆运算/康托展开 编辑

  例1 {1,2,3,4,5}的 全排列,并且已经从小到大排序完毕
  (1)找出第96个数
  首先用96-1得到95
  用95去除4! 得到3余23
  有3个数比它小的数是4
  所以第一位是4
  用23去除3! 得到3余5
  有3个数比它小的数是4但4已经在之前出现过了所以第二位是5(4在之前出现过,所以实际比5小的数是3个)
  用5去除2!得到2余1
  有2个数比它小的数是3,第三位是3
  用1去除1!得到1余0
  有1个数比它小的数是2,第二位是2
  最后一个数只能是1
  所以这个数是45321
  (2)找出第16个数
  首先用16-1得到15
  用15去除4!得到0余15
  用15去除3!得到2余3
  用3去除2!得到1余1
  用1去除1!得到1余0
  有0个数比它小的数是1
  有2个数比它小的数是3 但由于1已经在之前出现过了所以是4(因为1在之前出现过了所以实际比4小的数是2)
  有1个数比它小的数是2 但由于1已经在之前出现过了所以是3(因为1在之前出现过了所以实际比3小的数是1)
  有1个数比它小得数是2 但由于1,3,4已经在之前出现过了所以是5(因为1,3,4在之前出现过了所以实际比5小的数是1)
  最后一个数只能是2
  所以这个数是1435

康托逆展开的代码(Pascal)/康托展开 编辑

  求n个数的全排列中第m大的组合:
  {n在20+就需要用高精度来做}
  program test_cator;
  var
  flag:array[1..20] of boolean;
  a:array[1..20] of qword;
  ans:array[1..20] of integer;
  n:integer;
  m,cator:qword;
  temp:integer;
  found:boolean;
  i,j:integer;
  function cal(x:integer):qword;
  var
  s:integer;
  begin
  cal:=1;
  for s:=1 to x do
  cal:=cal*s;
  end;
  begin
  fillchar(flag,sizeof(flag),false);
  readln(n,m);
  cator:=m-1;
  for i:=(n-1) downto 1 do
  begin
  found:=false;
  a[n-i]:=cator div cal(i);
  cator:=cator mod cal(i);
  temp:=0;
  j:=1;
  while (j<=n) and (not found) do
  if not flag[j] then
  begin
  inc(temp);
  if temp=(a[n-i]+1) then
  begin
  ans[n-i]:=j;
  found:=true;
  flag[j]:=true;
  end
  else
  inc(j);
  end
  else
  inc(j);
  end;
  for i:=1 to n-1 do
  write(ans[i],' ');
  for i:=1 to n do
  if not flag[i] then
  begin
  writeln(i);
  halt;
  end;
  end. 
  ​ 康托展开的代码(C语言)
  long int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
  int hash[10]={0};
  int cantor(int m,int n)
  {
  long int num=0,e;
  int temp;
  int i,j;int k;
  int xp;
  m=m-1;
  for(i=n-1;i>0;i--)
  {
  temp=0;e=1;
  xp=m/fac[i];
  m=m%fac[i];
  for(j=1;j<=xp+1;j++)
  if(hash[j]!=0)
  temp++;
  if(hash[temp+xp+1]!=0)
  for(j=temp+xp+2;j<=n;j++)
  {
  temp++;
  if(hash[j]==0)
  break;
  }
  for(j=1;j<=i;j++)
  e*=10;
  num+=(temp+xp+1)*e;
  hash[temp+xp+1]=1;
  for(k=1;k<=n;k++)
  printf("%d ",hash[k]);
  printf("n");
  }
  temp=0;
  for(i=1;i<=m+1;i++)
  if(hash[i]!=0)
  temp++;
  hash[temp+m+1]=1;
  num+=temp+m+1;
  return(num);
  }
  int main()
  {
  printf("%ldn",cantor(96,5));
  system("pause");
  return 0;
  }

康托展开和逆康托展开的实现(Java)/康托展开 编辑

康托展开:

  int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};
  int cantor(int[] a, int k) {
  int i, j, tmp, num = 0;
  for (i = 0; i < k; i++) {
  tmp = 0;
  for (j = i + 1; j < k; j++)
  if (a[j] < a[i])tmp++;
  num += fac[k - i - 1] * tmp;
  }
  return num;
  }

逆康托展开:

  int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};
  int[] uncantor(int x, int k) {
  int res[] = new int[9];
  int i, j, l, t;
  boolean h[] = new boolean[12];
  for (i = 1; i <= k; i++) {
  t = x / fac[k - i];
  x -= t * fac[k - i];
  for (j = 1, l = 0; l <= t; j++)
  if (!h[j])l++;
  j--;
  h[j] = true;
  res[i - 1] = j;
  }
  return res;
  }