康托展开及其应用

int32位 posted @ Mar 22, 2016 04:01:30 PM in algorithm , 1955 阅读
转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。

定义

公式为:

X = a[n - 1] * (n - 1)! + a[n - 2] * (n - 2)! + ... + a[0] * 0!,
其中, a[i]为整数，并且0 <= a[i] <= i, 0 <= i < n, 表示当前未出现的的元素
中排第几个。

比如31254,

  • 在3后面比3小的有2个，分别为1,2
  • 在1后面比1小的有0个
  • 在2后面比2小的有0个
  • 在5后面比5小的有1个，为4
  • 在4后面比4小的有0个

因此a数组序列为2 0 0 1 0

X = 2 * 4! + 0 * 3! + 0 * 2! + 1 * 1! + 0 * 0!
  = 2 * 24 + 1
  = 49

既然是双射关系那一定可以反推出来31254这个序列。 首先我们需要推出a序列。

  • 49 / 4! = 2,因此a[4] = 2, 此时49 % 4! = 1,
  • 1 / 3! = 1 / 2! = 0,因此a[3] = a[2] = 0,
  • 而 1 / 1 = 1, 因此a[1] = 1,1 % 1! = 0,
  • 0 / 0! = 0,因此a[0] = 0
  • 所以得到a数组为2 0 0 1 0

再由a数组推出序列，根据a数组的意义反推。

  • a[4] = 2, 表示它在1 2 3 4 5 序列中比它小的有2个，即它自己排第3，它等于3
  • a[3] = 0, 表示它在1 2 4 5序列中比它小的有0个，即最小数，等于1
  • a[2] = 0, 表示它在2 4 5 中最小，等于2
  • a[1] = 1, 表示它在4 5中比它小的有一个，即排第2,等于5
  • a[0] = 0, 表示它在4中最小，只能是4

因此序列为3 1 2 5 4

应用

一个直观的应用就是给定一个自然数集合和一个序列，求这个序列中按从小到大的顺序 排第几个?

比如1 2 3 4 5, 3 1 2 5 4比它小的序列有49个，即它排第50

另一个应用就是逆推第K个排列是多少，比如第50个全排列是多少？则首先减1得到49, 再反推即可得到3 1 2 5 4

另外在保存一个序列，我们可能需要开一个数组，如果能够把它映射成一个自然数， 则只需要保存一个整数，大大压缩空间.

计算

计算包括编码（根据序列求对应的自然数）和解码（康托展开）。

编码

static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int cantor(int *a, int n)
{
    assert(n < 10);
    int x = 0;
    for (int i = 0; i < n; ++i) {
        int smaller = 0;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[i])
                smaller++;
        }
        x += FAC[n - i - 1] * smaller;
    }
    return x;
}

解码

int decantor(int *a, int n, int k)
{
    int *num = malloc(sizeof(int) * n );
    int len = n;
    for (int i = 0; i < n; ++i)
        num[i] = i + 1;
    int cur = 0;
    for (int i = n - 1; i > 0; --i) {
        int index = k / FAC[i];
        k %= FAC[i];
        a[cur++] = num[index];
        listRemove(num, &len, index);
    }
    a[cur] = num[0];
    free(num);
    return 0;
}

 

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！
  • 无匹配
  • 无匹配
Small_feed 评论 (6)
1
[回复]
CG HS Question Paper 说:
2022年9月05日 20:05

CG Board Model Paper 2023 Class 12 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. CG HS Question Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

2
[回复]
CGBSE Question Paper 说:
2022年9月05日 20:07

CG Board Model Paper 2023 Class 12 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. CGBSE Question Paper Class 12 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

3
[回复]
Bushra 说:
2022年12月27日 18:14

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. magic mushrooms for sale

4
[回复]
Bushra 说:
2022年12月28日 21:32

I found your this post while searching for some related information on blog search...Its a good post..keep posting and update the information. junk car removal vancouver

5
[回复]
Bushra 说:
2022年12月29日 19:59

Thank you so much Love your blog.. Yeh Rishta Kya Kehlata Hai

6
[回复]
Alyssa 说:
2023年1月09日 13:09

The Cantor expansion is a way of representing a positive real number as a sum of one or more terms, each of which is a certain power of a certain positive integer. The expansion is best online engagement rings store named after Georg Cantor, who first described it in 1874. The Cantor expansion of a positive real number is unique, meaning that there is only one way to represent a given number using this method. However, the expansion is not always finite. In other words, some numbers can be represented using a finite number of terms, while others may require an infinite number of terms.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter