概括“下一个排列”功能

Question

下面是返回按字典顺序排列的下一个排列的函数的实现。这对于欧拉问题之一很有用。

它是为在字符串上工作而编写的（我需要它）。但是，它应该适用于可比较值的任何索引序列。我尝试通过将两次出现的 String 更改为 IndexedSeq[Char] 来概括它，但这会出现错误：

euler-lib.scala:26: error: type mismatch;
 found   : IndexedSeq[Char]
 required: String
      ((n.slice(pivot+1, successor):+ n(pivot)) + n.drop(successor+1)).reverse
                                                        ^

为什么类型推断器在那里推断出 String ？我好像没有做过任何需要String的操作？

我可以通过使用 IndexedSeq["something-comparable"] 使其更加通用吗？我没能完成这项工作。

  // return the lexographically next permutation to the one passed as a parameter
  // pseudo-code from an article on StackOverflow
  def nextPermutation(n:String):String = {
  // 1. scan the array from right-to-left
  //1.1. if the current element is less than its right-hand neighbor,
  //    call the current element the pivot,
  //    and stop scanning
  // (We scan left-to-right and return the last such).
    val pivot = n.zip(n.tail).lastIndexWhere{ case (first, second) => first < second }

  //1.2. if the left end is reached without finding a pivot,
  //    reverse the array and return
  //    (the permutation was the lexicographically last, so its time to start over)
    if (pivot < 0) return n.reverse

  //2. scan the array from right-to-left again,
  //   to find the rightmost element larger than the pivot
  //  (call that one the successor)
    val successor = n.lastIndexWhere{_ > n(pivot)}

  //3. swap the pivot and the successor, and
  //4. reverse the portion of the array to the right of where the pivot was found
    return (n.take(pivot) :+ n(successor)) +
      ((n.slice(pivot+1, successor):+ n(pivot)) + n.drop(successor+1)).reverse
  }

Answer 1

IndexedSeq 中的方法 + 用于生成一个包含一个附加给定元素的新序列，但您希望生成一个包含附加序列的序列。其方法是 ++ 因此你的最后一行必须如下所示：

(n.take(pivot) :+ n(successor)) ++
  ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse

你看到这个奇怪的编译器消息，关于需要 String 因为 + 的签名不匹配，因此用于字符串连接的显式转换启动（此转换之所以存在，是因为它允许您编写类似 List(8) + " Test" 的内容）。

编辑：有序元素的序列类型的泛化：

正如我在评论中所说，序列的泛化有点复杂。除了元素类型 A 之外，您还需要另一种类型 CC[X] <: SeqLike[X,CC[X]] 来表示序列。通常 C <: SeqLike[A,C] 就足够了，但类型推断器不喜欢那个（您总是需要传递 A 和 < code>C 调用该方法时）。

如果您只是以这种方式更改签名，编译器会抱怨它需要隐式 CanBuildFrom[CC[A],A,CC[A]] 参数，因为 需要该参数反向方法。该参数用于从另一种序列类型构建一种序列类型 - 只需搜索站点即可查看集合 API 如何使用它的一些示例。

最终结果如下所示：

import collection.SeqLike
import collection.generic.CanBuildFrom

def nextPermutation[A, CC[X] <: SeqLike[X,CC[X]]](n: CC[A])(
  implicit ord: Ordering[A], bf: CanBuildFrom[CC[A],A,CC[A]]): CC[A] = {

  import ord._
  // call toSeq to avoid having to require an implicit CanBuildFrom for (A,A)
  val pivot = n.toSeq.zip(n.tail.toSeq).lastIndexWhere{
    case (first, second) => first < second
  }

  if (pivot < 0) {
    n.reverse
  }
  else {
    val successor = n.lastIndexWhere{_ > n(pivot)}
    (n.take(pivot) :+ n(successor)) ++
    ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse
  }
}

这样，如果您将一个传递给该方法，您将获得一个 Vector[Int]；如果您将其传递给该方法，您将获得一个 List[Double]方法。那么 String 又如何呢？这些不是实际的序列，但可以隐式转换为 Seq[Char]。可以改变该方法的定义，期望某种可以隐式转换为 Seq[A] 的类型，但类型推断将无法可靠地工作 - 或者至少我无法使其可靠地工作。作为一个简单的解决方法，您可以为 String 定义一个附加方法：

def nextPermutation(s: String): String =
  nextPermutation[Char,Seq](s.toSeq).mkString

Answer 2

这里的小提示：

n(pivot)) + n.drop(successor+1)
                  ^

当您收到类型不匹配错误时，^ 指向最后一个参数列表的第一个括号（即，它将指向第二个 ( x.foldLeft(y)(z))，这意味着该方法返回的值的类型错误，

或者在本例中为 n.drop。 (sucessor+1) 的类型为 IndexedSeq[Char]，但 + 方法需要一个 String

另一个小提示：唯一接受 + 的是数字类和 String 如果您尝试添加内容并收到错误，很可能是 Scala 认为您正在使用 +。 添加字符串 例如：

true + true // expected String, got Boolean error
"true" + true // works, the second true is converted to String
true + "true" // works, the first true is converted to String

因此，除非您使用数字或字符串，否则请避免使用+

因此，关于使其通用...

def nextPermutation[A <% Ordered[A]](n: IndexedSeq[A]): IndexedSeq[A] = {
  val pivot = n.zip(n.tail).lastIndexWhere{ case (first, second) => first < second }
  if (pivot < 0) return n.reverse
  val successor = n.lastIndexWhere{_ > n(pivot)}
  return (n.take(pivot) :+ n(successor)) ++
    ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse
}

简单的部分。只是声明IndexedSeq，但是您必须对A进行参数化，并且必须有一种方法对A进行排序，以便您可以比较元素。 （<% 表示存在从 A 到 Ordered[A] 的隐式转换）。另一种声明方式是这样的：

def nextPermutation[A : Ordering](n: IndexedSeq[A]): IndexedSeq[A] = {
  val ordering = implicitly[Ordering[A]]; import ordering._
  val pivot = n.zip(n.tail).lastIndexWhere{ case (first, second) => first < second }
  if (pivot < 0) return n.reverse
  val successor = n.lastIndexWhere{_ > n(pivot)}
  return (n.take(pivot) :+ n(successor)) ++
    ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse
}

这里，A : Ordering 意味着有一个隐式的 Ordering[A] 可用，然后获取该值并将其导入到作用域中，因此它可以提供隐式转换以使 < 工作。 Ordered[A] 和 Ordering[A] 之间的区别可以在其他问题中找到。

Answer 3

第24题让我难住了一段时间：

println("0123456789".permutations.drop(1000000 - 1).next);

Answer 4

该代码在 Scala 2.8.0 中为我编译正确。您使用的是哪个版本的 Scala？

scala> nextPermutation("12354")
res0: String = 12435