推广“下一个排列”功能 [英] Generalising a "next permutation" function

问题描述

下面是一个函数的实现，它返回词汇上的下一个排列。这在欧拉问题中很有用。

它被写入用于Strings（我需要它）。但是，它应该可以在任何可比较值的索引序列上工作。我尝试了通过将两个字符串更改为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 [可比较的东西]使它更通用吗？

  //将名词性下一个排列返回为参数
 //从StackOverflow上的文章获得伪代码
 def nextPermutation（n：String）：String = {
 // 1.从右到左扫描数组
 / /1.1。如果当前元素小于它的右侧邻居，
 //调用当前元素的枢轴，
 //并停止扫描
 //（我们从左到右扫描并返回最后这样）。 
 val pivot = n.zip（n.tail）.lastIndexWhere {case（first，second）=>第一&第二个} 
 
 //1.2。如果左端没有找到枢轴，
 //反转数组并返回
 //（排列是字典顺序的最后一个，所以它的时间重新开始）
 if（pivot < 0）return n.reverse 
 
 // 2。再次从右到左扫描数组，
 //找到大于数据透视元的最右元素
 //（称之为后继数）
 val后继数= n.lastIndexWhere { _> n（数据透视）} 
 
 // 3。交换枢轴和后继者，以及
 // 4。将数组中的部分倒转到找到主键的位置
 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（后继者+ 1））。reverse 
  

您将看到有关的奇怪编译器消息字符串因为 + 的签名不匹配，因此用于字符串连接的显式转换将启用（此转换在那里，因为它可以让你写下类似于 List（8）+Test）。





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

正如我在评论中所说的，对序列的泛化有点复杂。除了元素类型 A 之外，还需要另一个类型 CC [X] <：SeqLike [X，CC [X]] 表示序列。通常 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 ]，A，CC [A]]）：CC [A] = {
 
 import ord._ 
 //调用seq以避免需要隐式CanBuildFrom for（A，A ）
 val pivot = n.toSeq.zip（n.tail.toSeq）.lastIndexWhere {
 case（first，second）=>第一&第二个
} 
 
 if（pivot <0）{
 n.reverse 
} 
 else {
 val后继者= n.lastIndexWhere {_> n（pivot）} 
（n.take（pivot）：+ n（后继））++ 
（（n.slice（pivot + 1，successor）：+ n（pivot））++逆向
 
 
 code 
 
 
 
这样，如果你传递一个方法给一个 Vector [Int] 并且一个列表[Double] 把它传给了这个方法。那么 String  s？这些不是实际的序列，但可以隐式转换为 Seq [Char] 。可以改变该方法的定义，期望某种类型可以隐式转换为 Seq [A] ，但是再次类型推断不能可靠地工作 - 或者至少是I无法使其可靠工作。作为一个简单的解决方法，您可以为字符串 s定义一个附加方法： 
 
 
  def nextPermutation（s：String）：String = 
 nextPermutation [Char，Seq]（s.toSeq）.mkString 
  
 
Below is an implementation of a function that returns the lexographically next permutation. This is useful in one of the Euler problems. 


It's written to work on Strings (which I needed for that). However, it should work on any indexed sequence of comparable values. I've tried generalising it by changing the two occurrences of String to IndexedSeq[Char], but this gets an error:
euler-lib.scala:26: error: type mismatch;
 found   : IndexedSeq[Char]
 required: String
      ((n.slice(pivot+1, successor):+ n(pivot)) + n.drop(successor+1)).reverse
                                                        ^
Why has the type inferencer inferred String there? I don't seem to have done any operation that requires a String?

And can I make it more general still by having IndexedSeq["something-comparable"]? I've not been able to make this work.
  // 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
  }

解决方案
The method + in IndexedSeq is used to produce a new sequence containing one additional given element but you want to produce one containing an additional sequence. The method for this is ++ thus your last line must look like this:
(n.take(pivot) :+ n(successor)) ++
  ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse
You are seeing this strange compiler message about a String being expected because +'s signature does not match and thus an explicit conversion used for String concatenation kicks in (this conversion is there because it lets you write something like List(8) + " Test").

EDIT: Generalization over sequence types of ordered elements:

As I said in the comments, generalization over sequences is a bit more complicated. In addition to your element type A you will need another type CC[X] <: SeqLike[X,CC[X]] that represents the sequence. Normally C <: SeqLike[A,C] would be sufficient but the type inferencer does not like that one (you would always need to pass the types of A and C when calling that method).

If you just change your signature that way the compiler will complain that it requires an implicit CanBuildFrom[CC[A],A,CC[A]] parameter as that one is needed e.g. by the reverse method. That parameter is used to build one sequence type from another one - just search the site to see some examples of how it is used by the collections API.

The final result would look like this:
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
  }
}
This way you get a Vector[Int] if you passed one to the method and a List[Double] if you passed that to the method. So what about Strings? Those are not actual sequences but they can be implicitly converted into a Seq[Char]. It is possible alter the definition of that method expect some type that can be implicitly converted into a Seq[A] but then again type inference would not work reliably - or at least I could not make it work reliably. As a simple workaround you could define an additional method for Strings:
def nextPermutation(s: String): String =
  nextPermutation[Char,Seq](s.toSeq).mkString


                        
这篇关于推广“下一个排列”功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！