我将在这个答案中回答你问题的一半——“unranking”。目标是高效地找到一个有序字符串 [abcd…] 的字典序第 'K' 个排列。
为此,我们需要了解阶乘数系统(factoradics)。阶乘数系统使用阶乘值而不是数字的幂(二进制系统使用2的幂,十进制系统使用10的幂)来表示位值(或基数)。
位值(基数)如下:
5!= 120 4!= 24 3!=6 2!= 2 1!=1 0!=1 etc..
第0位数字始终为0。第1位数字(基数=1时!)可以是0或1。第2位数字(基数=2时!)可以是0、1或2,以此类推。一般来说,第n位数字可以取0-n之间的任何值。
表示为阶乘进制的前几个数字-
0 -> 0 = 0*0!
1 -> 10 = 1*1! + 0*0!
2 -> 100 = 1*2! + 0*1! + 0*0!
3 -> 110 = 1*2! + 1*1! + 0*0!
4 -> 200 = 2*2! + 0*1! + 0*0!
5 -> 210 = 2*2! + 1*1! + 0*0!
6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0!
7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0!
8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0!
9 -> 1110
10-> 1200
字符串的第n个字典序排列与其底数分解表示之间存在直接关系。
例如,以下是字符串“abcd”的排列。
0 abcd 6 bacd 12 cabd 18 dabc
1 abdc 7 badc 13 cadb 19 dacb
2 acbd 8 bcad 14 cbad 20 dbac
3 acdb 9 bcda 15 cbda 21 dbca
4 adbc 10 bdac 16 cdab 22 dcab
5 adcb 11 bdca 17 cdba 23 dcba
我们可以仔细观察这个模式。第一个字母在每6个排列(3!)后发生改变。第二个字母在2个排列(2!)后发生改变。第三个字母在每个排列(1!)后发生改变,第四个字母在每个排列(0!)后发生改变。我们可以使用这个关系直接找到第n个排列。
一旦用factoradic表示法表示了n,我们考虑其中的每个数字,并从给定的字符串中加入一个字符到输出中。如果我们需要找到‘abcd’的第14个排列。14用factoradic表示 -> 2100。
从第一个数字开始 -> 2,字符串是‘abcd’。假设索引从0开始,在字符串中取位置为2的元素,并将其添加到输出中。
Output String
c abd
2 012
下一个数字 -> 1。字符串现在是'abd'。再次取出位置为1的字符并将其添加到输出中。
Output String
cb ad
21 01
下一个数字是0。字符串为'ad'。将位置1处的字符添加到输出中。
Output String
cba d
210 0
下一个数字->0。字符串为‘d’。将位置0处的字符添加到输出中。
输出 字符串
cbad ''
2100
要将给定的数字转换为阶乘数系统,依次将该数字除以1、2、3、4、5等,直到商为零。每一步的余数形成了因子表示法。
例如,将349转换为因子表示法:
Quotient Reminder Factorial Representation
349/1 349 0 0
349/2 174 1 10
174/3 58 0 010
58/4 14 2 2010
14/5 2 4 42010
2/6 0 2 242010
349的阶乘表示是242010。