int32bit
公告
外部文章迁移完毕文章分类
最新评论
最新留言
友情链接
RSS
功能
热门文章
随机文章
存档
访问次数
328230
康托展开及其应用
int32位
posted @ Mar 22, 2016 04:01:30 PM
in algorithm
, 1860 阅读
转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！
转载请注明：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;
}
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.
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.
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
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
2022年12月29日 19:59
Thank you so much Love your blog.. Yeh Rishta Kya Kehlata Hai
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.