Generalising a "next permutation" function

Question

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
  }

Answer 1

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

Answer 2

Little tip here:

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

When you get a type mismatch error, and the ^ points to the first parenthesis of the last argument list (ie, it would point to the second ( in x.foldLeft(y)(z)), that means the value returned by that method has the wrong type.

Or, in this case, n.drop(sucessor+1) has type IndexedSeq[Char], but the + method expects a String.

Another little tip: the only things that accept + are the numeric classes and String. If you try to add things and get an error, most likely it is Scala thinking you are using + to add Strings. For example:

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

So, avoid + unless you are working with numbers or strings.

So, about making that general...

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
}

The easy part is just declaring IndexedSeq. But you have to parameterize on A, and there must be a way to order A so that you can compare the elements (<% means there's an implicit conversion from A to an Ordered[A] available). Another way to declare it would be like this:

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
}

Here, A : Ordering means there is an implicit Ordering[A] available, which is then obtained and imported into scope, so that it can offer implicit conversions to make < work. The difference between an Ordered[A] and an Ordering[A] can be found on other questions.