[关闭]
@jtahstu 2017-06-08T08:40:17.000000Z 字数 2246 阅读 306

康托展开和逆康托展开

算法


康托展开

详述

康托展开的公式是

X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 

其中,ai为当前未出现的元素中是排在第几个(从0开始)。

意义

康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。

例子

例如,有一个数组 s = ["A", "B", "C", "D"],它的一个排列 s1 = ["D", "B", "A", "C"],现在要把 s1 映射成 X。

n 指的是数组的长度,也就是4,所以
X(s1) = a4*3! + a3*2! + a2*1! + a1*0!

关键问题是 a4、a3、a2 和 a1 等于啥?

a4 = "D" 这个元素在子数组["D","B","A","C"]中是第几大的元素。"A"是第0大的元素,"B"是第1大的元素,"C"是第2大的元素,"D"是第3大的元素,所以 a4 = 3。

a3 = "B" 这个元素在子数组["B","A","C"]中是第几大的元素。"A"是第0大的元素,"B"是第1大的元素,"C" 是第2大的元素,所以 a3 = 1。

a2 = "A" 这个元素在子数组 ["A", "C"] 中是第几大的元素。"A"是第0大的元素,"C"是第1大的元素,所以 a2 = 0。

a1 = "C" 这个元素在子数组 ["C"] 中是第几大的元素。"C" 是第0大的元素,所以 a1 = 0。(因为子数组只有1个元素,所以a1总是为0)

所以,X(s1) = 3*3! + 1*2! + 0*1! + 0*0! = 20

逆康托展开

详述

如果已知 s = ["A", "B", "C", "D"],X(s1) = 20,能否推出 s1 = ["D", "B", "A", "C"] 呢?

意义

就是根据某个排列的在总的排列中的名次来确定这个排列。

例子

因为已知 X(s1) = a4*3! + a3*2! + a2*1! + a1*0! = 20,所以问题变成由 20 能否唯一地映射出一组 a4、a3、a2、a1?如果不考虑 ai 的取值范围,有
3*3! + 1*2! + 0*1! + 0*0! = 20
2*3! + 4*2! + 0*1! + 0*0! = 20
1*3! + 7*2! + 0*1! + 0*0! = 20
0*3! + 10*2! + 0*1! + 0*0! = 20
0*3! + 0*2! + 20*1! + 0*0! = 20
等等。但是满足 0 <= ai <= n-1 的只有第一组。可以使用辗转相除的方法得到 ai,如下图所示:
逆康托展开

代码实现

  1. # author: jtusta
  2. # contact: root@jtahstu.com
  3. # site: http://www.jtahstu.com
  4. # software: RubyMine
  5. # time: 2017/6/8 14:35
  6. class Cantor
  7. @@fac = Array.new 25,0
  8. def initialize(n)
  9. @@fac[0] = 1
  10. for i in 1..n-1
  11. @@fac[i] = @@fac[i-1]*i
  12. end
  13. end
  14. # 康托展开,根据给出的数组,求第多少大
  15. def cantor(list,len)
  16. ans = 0
  17. for i in 0..len-1
  18. cnt = 0
  19. for j in i+1..len-1
  20. if list[j]<list[i]
  21. cnt += 1
  22. end
  23. end
  24. ans += cnt*@@fac[len-i-1]
  25. end
  26. ans
  27. end
  28. # 逆康托展开,根据是多少大,找出数组是多少
  29. def cantorInver(n,len)
  30. subset = [] # 当前剩余的子集
  31. res = []
  32. for i in 1..len
  33. subset << i
  34. end
  35. i = len
  36. while(i>0)
  37. r = n%@@fac[i-1]
  38. t = n/@@fac[i-1]
  39. n = r
  40. subset = subset.sort()
  41. res << subset[t]
  42. subset.delete(subset[t])
  43. i -= 1
  44. end
  45. res
  46. end
  47. # 生成全排列
  48. def fullPermutation(len)
  49. endf = @@fac[len]-1
  50. for i in 0..endf
  51. print i,'->',cantorInver(i,len)
  52. puts
  53. end
  54. end
  55. end
  56. cantor = Cantor.new(20)
  57. list = [3,2,4,1]
  58. len = 4
  59. p cantor.cantor(list,len)
  60. p cantor.cantorInver(cantor.cantor(list,len),len)
  61. p cantor.fullPermutation(4)

执行结果

  1. /usr/bin/ruby -e $stdout.sync=true;$stderr.sync=true;load($0=ARGV.shift) /Users/jtusta/Documents/Code/Ruby/algorithm/cantor.rb
  2. 15
  3. [3, 2, 4, 1]
  4. 0->[1, 2, 3, 4]
  5. 1->[1, 2, 4, 3]
  6. 2->[1, 3, 2, 4]
  7. 3->[1, 3, 4, 2]
  8. 4->[1, 4, 2, 3]
  9. 5->[1, 4, 3, 2]
  10. 6->[2, 1, 3, 4]
  11. 7->[2, 1, 4, 3]
  12. 8->[2, 3, 1, 4]
  13. 9->[2, 3, 4, 1]
  14. 10->[2, 4, 1, 3]
  15. 11->[2, 4, 3, 1]
  16. 12->[3, 1, 2, 4]
  17. 13->[3, 1, 4, 2]
  18. 14->[3, 2, 1, 4]
  19. 15->[3, 2, 4, 1]
  20. 16->[3, 4, 1, 2]
  21. 17->[3, 4, 2, 1]
  22. 18->[4, 1, 2, 3]
  23. 19->[4, 1, 3, 2]
  24. 20->[4, 2, 1, 3]
  25. 21->[4, 2, 3, 1]
  26. 22->[4, 3, 1, 2]
  27. 23->[4, 3, 2, 1]
  28. Process finished with exit code 0
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注