给定词典索引查找数值排列的算法

Question

我正在寻找一种算法，它给定一组数字(例如 1 2 3)和一个索引(例如 2)，然后根据字典顺序对这些数字进行第二次排列。例如，在这种情况下，算法将返回 1 3 2。

Answer 1

下面是一个 Scala 中的示例解决方案，我将对其进行详细解释:

/**
    example: index:=15, list:=(1, 2, 3, 4)
*/ 
def permutationIndex (index: Int, list: List [Int]) : List [Int] = 
  if (list.isEmpty) list else {
    val len = list.size     // len = 4
    val max = fac (len)     // max = 24
    val divisor = max / len // divisor = 6
    val i = index / divisor // i = 2
    val el = list (i)
    el :: permutationIndex (index - divisor * i, list.filter (_ != el)) }

由于 Scala 不是那么出名，我想我必须解释一下算法的最后一行，除此之外，它是非常不言自明的。

    el :: elist

从元素 el 和列表 elist 构造一个新列表。 Elist 是一个递归调用。

    list.filter (_ != el)

只是没有元素 el 的列表。

用一个小列表对其进行详尽测试:

(0 to fac (4) - 1).map (permutationIndex (_, List (1, 2, 3, 4))).mkString ("\n")

使用 2 个示例测试更大列表的速度:

scala> permutationIndex (123456789, (1 to 12).toList) 
res45: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 6, 9, 3)

scala> permutationIndex (123456790, (1 to 12).toList) 
res46: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6)

结果立即出现在一台使用了 5 年的笔记本电脑上。 12 个元素的列表有 479 001 600 个排列，但是对于 100 或 1000 个元素，这个解决方案应该仍然可以快速工作——你只需要使用 BigInt 作为索引。

它是如何工作的？我制作了一个图形，以可视化示例，一个列表 (1, 2, 3, 4) 和一个索引 15:

4 个元素的列表产生 4 个!排列(= 24)。我们选择一个从 0 到 4 的任意索引!-1，比方说 15。

我们可以将树中的所有排列可视化，第一个节点来自 1..4。我们分4!通过 4 并看到，每个第一个节点导致 6 个子树。如果我们将索引 15 除以 6，则结果为 2，而索引为 2 的从零开始的列表中的值为 3。因此第一个节点为 3，列表的其余部分为 (1, 2, 4) .这是一个表格，显示了 15 如何导致数组/列表/其他中索引为 2 的元素:

0 1 2 3 4 5 | 6 ... 11 | 12 13 14 15 16 17 | 18 ... 23
     0      |     1    |         2         |     3
            |          | 0  1  2  3  4  5  |

我们现在减去 12，最后 3 个元素的单元格 (12...17) 的第一个元素，它有 6 种可能的排列，看看 15 如何映射到 3。数字 3 导致数组索引 1现在，它是元素 2，所以目前的结果是 List (3, 2, ...)。

                        | 0 1 | 2 3 | 4 5 |
                        |  0  |  1  |  3  |
                              | 0 1 |

同样，我们减去 2，并以 2 个具有 2 个排列和索引 (0, 3) 的剩余元素结束，映射到值 (1, 4)。我们看到，属于从上往下第 15 个的第二个元素映射到值 3，最后一步的剩余元素是另一个:

                             | 0 | 1 |
                             | 0 | 3 |
                             | 3 | 0 |

我们的结果是 List(3, 2, 4, 1) 或索引 (2, 1, 3, 0)。按顺序测试所有索引表明，它们按顺序产生所有排列。