字典序排列

Question

我一直在解决欧拉计划问题24，并找到了一个用Scala编写的解决方案（我本来想自己解决的）。我原打算自己解决，但现在着迷于弄清楚这个解决方案是如何工作的。

问题：

0、1和2的字典排列为：

012、021、102、120、201和210。

数字0、1、2、3、4、5、6、7、8和9的第1000000个字典排列是什么？

解决方案：

def permutations(s : String) : Seq[String] =
{
  if(s.size == 1)
    Seq(s);
  else
    s.flatMap(x => permutations(s.filterNot(_ == x)).map(x +));
}

val ans = permutations("0123456789")(1000000 - 1).toLong;

println(ans);

- Draconian Times

---

一个更有趣的问题是第一万亿个元素是什么（假设是更大的字母表），因为这将迫使你真正地找出模式。 - Mysterious Dan

那段代码如果用for推导式写会更加清晰易懂。 - Mysterious Dan

Answer 1

这在Scala中非常简单：

"0123456789".permutations.drop(999999).next

- flavian

---

不错的简洁解决方案 ;) - Draconian Times

Answer 2

可能看一下下面的功能性实现会很有启发（尽管它不能按字典顺序产生排列）。

在接下来的内容中，我将使用List而不是String，因为它们在函数编程中非常普遍，并且有助于考虑“递归解决方案”。列表可以是空的Nil，或者包含第一个元素（列表头）和其余列表（列表尾部）x :: xs。

现在，解决涉及列表的问题的典型“功能性”方法是思考如何从xs的解决方案获取非空列表x::xs的解决方案。

在排列的情况下，问题是

假设我们有列表xs的所有排列，如何获得x::xs的所有排列？

示例：假设我们有List(1, 2)的所有排列，即

List(1, 2)
List(2, 1)

我们如何获取List(0, 1, 2)的所有排列，它们是

List(0, 1, 2)
List(1, 0, 2)
List(1, 2, 0)
List(0, 2, 1)
List(2, 0, 1)
List(2, 1, 0)

仔细观察可以发现，我们只是在解决方案List(1, 2)中以所有可能的方式插入了0。

因此，如果我们有一个函数，它可以产生将单个元素插入到给定列表中的所有可能结果——让我们称之为inserts——那么一种解决方案可能如下所示：

def permutations[A](xs: List[A]) : List[List[A]] = xs match { 
  case Nil => List(Nil)
  case x::xs => permutations(xs).flatMap(inserts(x, _))
}

也就是说，如果给定的列表 xs 是空的，那么只有一种排列，即空列表。否则，我们首先通过递归调用计算出 xs 的所有排列，然后以所有可能的方式将 x 插入到得到的列表中。

生成将 x 插入到列表 ys 中所有可能位置的函数可以如下所示：

def inserts[A](x: A, ys: List[A]) : List[List[A]] = ys match {
  case Nil => List(List(x))
  case y::ys => (x::y::ys) :: inserts(x, ys).map(y::_)
}

如果ys是空的，则结果只是单例列表List(x)。否则，我们再次“递归思考”，即假设我们有所有可能将x插入到ys中的情况，如何获得将x插入到y::ys中的所有可能情况？首先，在所有解决方案的前面添加y--inserts(x, ys).map(y::_)--得到所有以y开头的解决方案；然后添加x::y::ys作为第一个元素的解决方案。

注意：当然，这个解决方案与Project Euler所要求的结果顺序不同。这就是初始帖子中的解决方案“混合”计算较小列表的排列和使用它们生成完整列表的排列的原因。在这里，较小的“列表”是s.filterNot(_ == x)（至少比s短一个元素，因为x是s的一个元素），被用于递归。

- chris

Answer 3

这是一段命令式的伪代码，用于解释你提供的解决方案：

foreach (x: s) { // flatMap in the code
  val lst = permutations(all character of s except x) // permutations(s.filterNot(_ == x)) in the code
  foreach (permutation: lst) { // map in the code
    append(x, permutation) // (x +) in the code
    // example: x = "0" and permutation = "21" yield "021"
  }
}

- Ayoub

Answer 4

这一切归结于如何对的排列进行分类： 您可以通过它们的第一个字符将排列分组。由于在此类组内第一个字符是固定的，因此该组基本上是：第一个字符+所有其他字符的排列。那就是算法的归纳步骤。基本步骤只是单个元素的排列只有一个。

如果您查看Scala代码：

// this is the base step
if(s.size == 1)
  Seq(s)

递归步骤如下：

• 对于字符串s中的每个字符x，
• 计算出其他字符的所有排列permutations,
• 在每个排列的前面重新添加x,
• 这样你就得到了以x开头的所有排列。
• 将所有这些组合在一起（扁平化）。

因此：

s.flatMap(x => permutations(s.filterNot(_ == x)).map(x + _))

- gourlaysama

---

这帮助我了解代码在做什么，虽然我暂时还不能用这种方式思考编程...不过很快就能了 :) - Draconian Times