推广"下一个排列"功能

Question

下面是一个函数的实现,它返回字典上的下一个排列.这在Euler问题中很有用.

它写的是在Strings上工作(我需要它).但是,它应该适用于任何可比较值的索引序列.我已经尝试通过将两次出现的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 ["可比较的东西"]使其更加通用吗？我没能做到这一点.

  // 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

您会看到这个奇怪的编译器消息，关于 aString是预期的，因为+的签名不匹配，因此用于字符串连接的显式转换开始（此转换之所以存在，是因为它允许您编写类似 的内容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]如果您将它传递给该方法，您就会得到一个。那么Strings呢？这些不是实际的序列，但它们可以隐式转换为Seq[Char]. 可以改变该方法的定义，期望某种可以隐式转换为 a 的类型Seq[A]，但类型推断将无法可靠地工作 - 或者至少我无法使其可靠地工作。作为一个简单的解决方法，您可以为 s 定义一个附加方法String：

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