dsa*_*ton 2 sorting recursion haskell lexicographic
我正在研究 Project Euler 的问题 24，如下所示：
排列是对象的有序排列。例如，3124 是数字 1、2、3 和 4 的一种可能排列。如果所有排列都按数字或字母顺序列出，我们将其称为字典顺序。0、1 和 2 的字典排列是：
012 021 102 120 201 210
数字 0、1、2、3、4、5、6、7、8 和 9 的第一百万个字典排列是什么？
我正在尝试使用 Haskell 来解决这个问题，并从暴力方法开始：
import Data.List
(sort . permutation) [0..9] !! 999999
但这花费的时间太长了，我想知道是否是因为程序首先获取所有排列，然后对它们进行排序，最后获取第百万个元素，这比它需要做的工作要多得多。
所以我想如果我要编写一个函数来枚举已经按字典顺序排列的排列，那么我可以加快速度，这样我们就可以停在第一百万个元素并得到答案。
我想到的算法是首先对输入列表进行排序x，然后取出第一个（最小的）元素并将其按字典顺序添加到其余元素的排列中。这些顺序可以通过在现在已经排序的尾部递归调用原始函数来找到x（这意味着我们的原始函数应该有一种方法来标记输入列表是否已排序）。然后我们继续处理下一个最大的元素，x依此类推，直到我们得到完整的有序列表。不幸的是，我仍然是 Haskell 初学者，我尝试编写这个函数失败了。关于如何做到这一点有任何提示吗？
我的想法对于评论来说太长了，但它并不是一个完整的可行解决方案。尽管如此，这个计划应该会立即生效。
首先按字典顺序生成排列。使用递归算法很容易做到这一点。首先，选择可用的最少元素，并递归地生成剩余元素的排列，将所选元素添加到每个排列的前面。然后按字典顺序选择第二个元素并继续向上。
就其价值而言，如果select输入列表按升序排序，那么这就是您经常在 Haskell 教学材料中找到的基于标准非确定性的排列算法。它不是所使用的算法Data.List.permutations，它的设计目的是通过无限输入更快、更高效。
但你可以做得更好。您不需要生成目标排列之前的所有排列。您可以跳过，事实证明这非常简单。
您需要做的就是查看您要定位的排列数量，我们将其称为k，并使用它来索引排列。如果输入按字典顺序排序，则结果的第一个元素是索引 处的元素q，后面是索引 处剩余元素的排列（r给定 ）(q, r) = divMod k (fact(n - 1))。
我确信有比这更快的方法，但是对于像一百万这样的小数字来说，这应该基本上是即时的。