Generalising a "next permutation" function

generics, permutation, scala, types

Solution

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 `String`s? 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 `String`s:

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

Problem

Original source