推广“下一个置换”函数

方法 + 在里面 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] 就足够了,但是类型推断器不喜欢这个(您总是需要传递 一个 和 C 当调用该方法时)。

如果您只是这样更改签名,编译器将抱怨它需要隐式 CanBuildFrom[CC[A],A,CC[A]] 所需的参数,例如 reverse 方法。该参数用于从另一个序列类型构建一个序列类型-只需搜索站点以查看collections 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] 如果你把它传给方法。所以呢 字符串 s?这些不是实际的序列,但可以隐式地转换为 Seq[Char] . 有可能改变该方法的定义,期望某些类型可以隐式转换为 Seq[A] 但是,类型推断仍然不能可靠地工作——或者至少我不能让它可靠地工作。作为一个简单的解决方法,您可以为 字符串 学生:

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

小贴士:

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

当出现类型不匹配错误时 ^ 指向最后一个参数列表的第一个括号(即,它将指向第二个 ( 在里面 x.foldLeft(y)(z) ),这意味着返回的值 用那种方法 类型错误。

或者,在这种情况下, n.drop(sucessor+1) 具有类型 IndexedSeq[Char] ,但是 + 方法需要 String .

另一个小提示:只有接受 + 是数值类和 字符串 . 如果您试图添加内容并得到一个错误,很可能是Scala认为您正在使用 + 添加 Strings . 例如:

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 ,而且一定有办法订购 一个 这样你就可以比较元素( <% 意味着有一个隐式的转换 一个 给一个 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] 可用,然后获取并导入到作用域中,以便它可以提供隐式转换 < 工作。两者的区别 命令的 还有一个 订购 可以在其他问题上找到。

这段代码在Scala 2.8.0中为我编译了correclty。你用的是哪一个版本的Scala?

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

问题24让我困惑了一段时间:

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