perm.scala

object Perm {
  // return the lexographically next permutation to the one passed as a parameter
  // pseudo-code from an article on StackOverflow
  def nextPermutation[A](n: IndexedSeq[A])(implicit ord: Ordering[A]): IndexedSeq[A] = {
    import ord._

  // 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) {
      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
    }
  }
}