3

我一直在研究 Project Euler问题 24 ，并在Scala中遇到了一个解决方案（无论如何我都试图解决它）。我本来打算自己做，但现在我对找出这个解决方案的工作原理感到震惊。

问题：

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

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

数字 0、1、2、3、4、5、6、7、8 和 9 的百万分之一字典排列是什么？

解决方案：

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);
4

4 回答 4

8

这在 Scala 中是微不足道的：

"0123456789".permutations.drop(999999).next
于 2013-08-01T12:22:50.740 回答
3

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

我将List在下面使用 s 代替Strings，因为它们在函数式编程中无处不在，并且有助于思考“递归解决方案”。一个列表要么是空的Nil，要么由第一个元素（列表的头部）和剩余的列表（列表的尾部）组成x :: xs。

现在，为涉及列表的问题准备解决方案的典型“功能性”方法是考虑如何x::xs从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)

仔细观察会发现，我们只是0以所有可能的方式将List(1, 2).

因此，如果我们有一个函数可以产生将单个元素插入给定列表的所有可能结果——让我们调用它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)。否则，我们再次“递归思考”，即假设我们有 into 的所有可能插入，x我们ys如何获得 into 的所有可能x插入y::ys？首先，我们y在所有解决方案的前面添加ys- - 产生所有以;inserts(x, ys).map(y::_)开头的解决方案 y然后我们添加x第一个元素的解决方案，即x::y::ys.

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

于 2013-08-02T02:48:33.703 回答
2

这一切都归结为您如何对 的排列进行分类s：

您可以按排列的第一个字符对排列进行分组。由于第一个字符固定在这样的组中，该组基本上是：第一个字符+所有其他字符的排列。这就是算法的归纳步骤。基本步骤只是单个元素只有一个排列。

如果您查看 Scala 代码：

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

递归步骤如下：

  • 对于 中的 每个字符x，s
    • 计算permutations所有其他的，
    • x在所有的开头重新添加，
    • 你得到所有从 . 开始的排列x。
  • 将所有这些组连接（展平）在一起。

因此：

s.flatMap(x => permutations(s.filterNot(_ == x)).map(x + _))
于 2013-08-01T12:36:14.227 回答
2

这是一个命令式等效伪代码，用于解释您提供的解决方案：

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"
  }
}
于 2013-08-01T11:00:44.143 回答