scala - 概括一个 "next permutation"函数

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 ？我好像没有做过任何需要字符串的操作？

我可以通过使用 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 和 C 的类型)。

如果你只是这样改变你的签名，编译器会提示它需要一个隐式 CanBuildFrom[CC[A],A,CC[A]]需要的参数，例如由 reverse方法。该参数用于从另一种序列类型构建一种序列类型 - 只需搜索站点即可查看集合 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 定义一个额外的方法。 s:

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