sorting - 使用 Haskell 按字典顺序获取排列

Question

我正在研究 Project Euler 的问题 24，如下所示:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

我正在尝试使用 Haskell 来解决这个问题，并从暴力方法开始:

import Data.List
(sort . permutation) [0..9] !! 999999

但这花费的时间太长了，我想知道是否是因为程序首先获取所有排列，然后对它们进行排序，最后获取第百万个元素，这比它需要做的工作要多得多。

所以我想如果我编写一个函数来枚举已经按字典顺序排列的排列，那么我可以加快速度，这样我们就可以停在第一百万个元素并得到答案。

我想到的算法是首先对输入列表 x 进行排序，然后取出第一个(最小的)元素并将其按字典顺序添加到其余元素的排列中。这些顺序可以通过在 x 现在已经排序的尾部递归调用原始函数来找到(这意味着我们的原始函数应该有一种方法来标记输入列表是否已排序)。然后我们继续使用 x 的下一个最大元素，依此类推，直到获得完整的有序列表。不幸的是，我仍然是 Haskell 初学者，我尝试编写这个函数失败了。关于如何做到这一点有任何提示吗？

Answer 1

我的想法太长，无法发表评论，但它并不是一个完整的可行解决方案。尽管如此，这个计划应该几乎立即生效。

首先按字典顺序生成排列。使用递归算法很容易做到这一点。首先，选择可用的最少元素，并递归地生成剩余元素的排列，将所选元素添加到每个排列的前面。然后按字典顺序选择第二个元素并继续向上。

就其值(value)而言，如果输入列表按升序排序，那么这就是您经常在 Haskell 教学 Material 中找到的基于标准非确定性select 的排列算法。它不是 Data.List.permutations 使用的算法，该算法旨在通过无限输入提高速度和效率。

但你可以做得更好。您不需要生成目标排列之前的所有排列。您可以跳过，事实证明这非常简单。

您需要做的就是查看您要定位的排列数量，我们将其称为k，并使用它来索引排列。如果输入按字典顺序排序，则结果的第一个元素是索引 q 处的元素，后面是索引 r 处剩余元素的排列，给定 (q, r) = divMod k (事实(n - 1))。

我确信有比这更快的方法，但是对于像一百万这样的小数字来说，这应该基本上是即时的。