DeCantor Expansion (逆康托展开)
Background\text{Background}Background
The \text{The }The Listen&Say
Test will be hold on May 11, so I decided to fill my blog \text{Test will be hold on May 11, so I decided to fill my blog }Test will be hold on May 11, so I decided to fill my blog
with English words until that day.\text{with English words until that day.}with English words until that day.
Problem\text{Problem}Problem
There goes a problem.\text{There goes a problem.}There goes a problem.
You’ve got 2 intergers N,k. Please calculate the kth permutation of ∀k∈[i,n].\text{You've got 2 intergers }N,k\text{. Please calculate the }k\text{th permutation of }\forall k\in[i,n].You’ve got 2 intergers N,k. Please calculate the kth permutation of ∀k∈[i,n].
Solution\text{Solution}Solution
It’s easy to know that we can got it by Depth-first Search, \text{It's easy to know that we can got it by Depth-first Search, }It’s easy to know that we can got it by Depth-first Search, but its Time complexity is O(n!).\text{but its Time complexity is }O(n!).but its Time complexity is O(n!).
DeCantor Expansion
is a algorithm which can solve problems like these calculating the kth permutation\text{is a algorithm which can solve problems like these calculating the }k\text{th permutation}is a algorithm which can solve problems like these calculating the kth permutationin O(nlogn) with heap optimization.\text{in }O(n\log n)\text{ with heap optimization.}in O(nlogn) with heap optimization.
Let’s explain how it works in a simple example. Set N=5,k=61, the answer is a[].\text{Let's explain how it works in a simple example. Set }N=5,k=61,\text{ the answer is }a[].Let’s explain how it works in a simple example. Set N=5,k=61, the answer is a[].
1.Let 61 / 4! = 2 ... 13, it shows that there’re 2 numbers behind a[1] are smaller than a[1].\text{1.\quad Let 61 / 4! = 2 ... 13, it shows that there're 2 numbers behind }a[1]\text{ are smaller than a[1].}1.Let 61 / 4! = 2 ... 13, it shows that there’re 2 numbers behind a[1] are smaller than a[1].
Therefore, a[1]=3;\text{Therefore, }a[1]=3;Therefore, a[1]=3;
2.Let 13 / 3! = 2 ... 1, it shows that there’re 2 numbers behind a[2] are smaller than a[2].\text{2.\quad Let 13 / 3! = 2 ... 1, it shows that there're 2 numbers behind }a[2]\text{ are smaller than a[2].}2.Let 13 / 3! = 2 ... 1, it shows that there’re 2 numbers behind a[2] are smaller than a[2].
Therefore, a[2]=4;\text{Therefore, }a[2]=4;Therefore, a[2]=4;
3.Let 1 / 2! = 0 ... 1, it shows that there’re 0 number behind a[3] are smaller than a[3].\text{3.\quad Let 1 / 2! = 0 ... 1, it shows that there're 0 number behind }a[3]\text{ are smaller than a[3].}3.Let 1 / 2! = 0 ... 1, it shows that there’re 0 number behind a[3] are smaller than a[3].
Therefore, a[3]=1;\text{Therefore, }a[3]=1;Therefore, a[3]=1;
4.Let 1 / 1! = 1 ... 0, it shows that there’re 1 number behind a[4] are smaller than a[4].\text{4.\quad Let 1 / 1! = 1 ... 0, it shows that there're 1 number behind }a[4]\text{ are smaller than a[4].}4.Let 1 / 1! = 1 ... 0, it shows that there’re 1 number behind a[4] are smaller than a[4].
Therefore, a[4]=5;\text{Therefore, }a[4]=5;Therefore, a[4]=5;
Therefore, a[5]=2,a[]={3,4,1,5,2}.\text{Therefore, }a[5]=2, a[]=\{3,4,1,5,2\}.Therefore, a[5]=2,a[]={3,4,1,5,2}.
Summary\text{Summary}Summary
∀i∈[1,n−1], let k / (n−1)!, the answer you’ve got is the number of interger j∈[i+1,n] which has a[j]<a[i]. And let k equals to the remainder.\forall i\in[1,n-1],\text{ let }k\ /\ (n-1)!\text{, the answer you've got is the number of interger }\newline j\in[i+1,n]\text{ which has }a[j]<a[i].\text{ And let }k\text{ equals to the remainder.}∀i∈[1,n−1], let k / (n−1)!, the answer you’ve got is the number of interger j∈[i+1,n] which has a[j]<a[i]. And let k equals to the remainder.
The End\text{The End}The End
Reference material\text{Reference material}Reference material
最新文章
- java 连接数据库之一个完整的函数
- C# Windows service 开发笔录
- css - position relative与display table-cell深入分析
- 利用反射得到android存储路径
- FloodLight使用感受
- Sql Server_笔记
- 003Linux网络配置
- vs中常用的快捷键
- c#中var关键字用法
- Elasticsearch安装ik中文分词插件(四)
- LeetCode OJ 199. Binary Tree Right Side View
- List<;Object>;中,以Object的某一属性值为参照进行排序,选取最大记录的解决办法
- Matlab 2014b For Mac安装破解
- Postman使用小技巧
- java http缓存
- C++回顾day03---<;多态>;
- gulp的使用(三)之把gulp运用到项目实战中
- JAVA日常之一
- Mysql数据表去重
- Django学习篇(web框架的由来)