scala – 推广“下一个排列”函数
|
下面是一个函数的实现,它返回字典上的下一个排列.这在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
}
解决方法
IndexedSeq中的方法用于生成包含一个额外给定元素的新序列,但您希望生成一个包含其他序列的元素.因此,最后一行必须如下所示：
(n.take(pivot) :+ n(successor)) ++ ((n.slice(pivot+1,successor):+ n(pivot)) ++ n.drop(successor+1)).reverse 你看到这个奇怪的编译器消息关于一个字符串是预期的,因为它的签名不匹配,因此用于字符串连接的显式转换启动(这种转换是因为它允许你写类似List(8)“Test”) . 编辑：对有序元素的序列类型进行泛化： 正如我在评论中所说,序列的泛化有点复杂.除了元素类型A之外,还需要另一种类型CC [X]<：SeqLike [X,CC [X]]来表示序列.通常C<：SeqLike [A,C]就足够了,但类型推断器不喜欢那个(在调用该方法时,你总是需要传递A和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],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].那么弦乐呢？那些不是实际的序列,但它们可以隐式转换为Seq [Char].有可能改变该方法的定义,期望某些类型可以隐式转换为Seq [A]但是再次类型推断不能可靠地工作 – 或者至少我无法使其可靠地工作.作为一个简单的解决方法,您可以为字符串定义另一种方法： def nextPermutation(s: String): String = nextPermutation[Char,Seq](s.toSeq).mkString （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |