c++ - 重复排列的排名和取消排名

Question

我正在阅读排列，我对排名/取消排名方法很感兴趣。

来自一篇论文的摘要:

A ranking function for the permutations on n symbols assigns a unique integer in the range [0, n! - 1] to each of the n! permutations. The corresponding unranking function is the inverse: given an integer between 0 and n! - 1, the value of the function is the permutation having this rank.

我使用 next_permutation 在 C++ 中创建了一个排名和一个非排名函数。但这对于 n>8 是不切实际的。我正在寻找一种更快的方法和 factoradics似乎很受欢迎。 但我不确定这是否也适用于重复项。那么，什么是对具有重复项的排列进行排名/取消排名的好方法？

Answer 1

我将在这个答案中涵盖您问题的一半 - “取消排名”。目标是高效地找到有序字符串 [abcd...] 的第 K 个字典排列。

为此，我们需要了解阶乘数系统 (factoradics)。阶乘数字系统使用阶乘值而不是数字的幂(二进制系统使用 2 的幂，十进制使用 10 的幂)来表示位值(或基数)。

位值(基数)是 –

5!= 120    4!= 24    3!=6    2!= 2    1!=1    0!=1 etc..

第零位的数字始终为 0。第一位的数字(基数 = 1!)可以是 0 或 1。第二位的数字(基数为 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 个排列。

一旦我们用因数表示法表示 n ，我们就会考虑其中的每个数字，并将给定字符串中的一个字符添加到输出中。如果我们需要找到“abcd”的第 14 个排列。 14 in factoradics -> 2100.

从第一个数字开始->2，字符串为‘abcd’。假设索引从 0 开始，从字符串中取出位置 2 的元素并将其添加到输出。

Output                    String
  c                         abd
  2                         012

下一个数字 -> 1.String 现在是“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。