Обобщая функцию "следующей перестановки"

Question

Ниже приведена реализация функции, которая возвращает лексографически следующую перестановку. Это полезно в одной из задач Эйлера.

Он написан для работы со строками (что мне было нужно для этого). Тем не менее, он должен работать на любой индексированной последовательности сопоставимых значений. Я попытался обобщить его, изменив два вхождения 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
                                                        ^

Почему вывод по типу выводит строку? Кажется, я не выполнил какую-либо операцию, требующую строку?

И могу ли я сделать его еще более общим, имея 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
  }

Answer 1

Метод + в IndexedSeq используется для создания новой последовательности, содержащей один дополнительный заданный элемент, но вы хотите создать последовательность, содержащую дополнительную последовательность. Метод для этого ++, поэтому ваша последняя строка должна выглядеть следующим образом:

(n.take(pivot) :+ n(successor)) ++
  ((n.slice(pivot+1, successor):+ n(pivot)) ++ n.drop(successor+1)).reverse

Вы видите это странное сообщение компилятора об ожидаемом String, потому что подпись + не совпадает, и, таким образом, включается явное преобразование, используемое для конкатенации строк (это преобразование существует, потому что оно позволяет вам написать что-то вроде List(8) + " Test").

РЕДАКТИРОВАТЬ: Обобщение по типам последовательности упорядоченных элементов:

Как я уже говорил в комментариях, обобщение последовательностей немного сложнее. В дополнение к вашему типу элемента A вам потребуется еще один тип CC[X] <: SeqLike[X,CC[X]], представляющий последовательность. Обычно C <: SeqLike[A,C] было бы достаточно, но средство вывода типов не понравилось бы такому (вам всегда нужно было бы передавать типы A и C при вызове этого метода).

Если вы просто измените свою подпись таким образом, компилятор будет жаловаться на то, что для нее требуется неявный параметр CanBuildFrom[CC[A],A,CC[A]], поскольку он необходим, например. по методу reverse. Этот параметр используется для создания одного типа последовательности из другого - просто найдите на сайте несколько примеров того, как он используется 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._
  // 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], если вы передадите его методу. Так что насчет String с? Это не фактические последовательности, но они могут быть неявно преобразованы в Seq[Char]. Можно изменить определение этого метода, ожидая некоторый тип, который может быть неявно преобразован в Seq[A], но опять же вывод типа не будет работать надежно - или, по крайней мере, я не смог бы заставить его работать надежно. В качестве простого обходного пути вы можете определить дополнительный метод для String s:

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

Answer 2

Небольшой совет:

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

Когда вы получаете ошибку несоответствия типов, и ^ указывает на первую скобку в списке последних аргументов (т. Е. Она указывает на вторую * 1005)* в x.foldLeft(y)(z)), это означает, что значение, возвращаемое этим методом , имеет неправильный тип.

Или, в этом случае, n.drop(sucessor+1) имеет тип IndexedSeq[Char], но + метод ожидает String.

Еще один маленький совет: единственные вещи, которые принимают +, это числовые классы и String.Если вы попытаетесь добавить что-то и получите ошибку, скорее всего, это Scala, которая думает, что вы используете + для добавления Strings.Например:

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

Итак, избегайте +, если только вы не работаете с числами или строками.

Итак, о том, как сделать это общее ...

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
}

Легкая часть просто объявляет IndexedSeq.Но вы должны параметризовать A, и должен быть способ упорядочить A, чтобы вы могли сравнивать элементы (<% означает, что имеется неявное преобразование из A в Ordered[A]).Другой способ объявить это будет выглядеть так:

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
}

Здесь A : Ordering означает, что существует неявный доступный Ordering[A], который затем получается и импортируется в область видимости, так что он может предлагать неявные преобразованиязаставить < работать.Разницу между Ordered[A] и Ordering[A] можно найти по другим вопросам.

Answer 3

Задача 24 на какое-то время поставила меня в тупик:

println("0123456789".permutations.drop(1000000 - 1).next);

Answer 4

Код компилирует для меня корректность в Scala 2.8.0.Какую версию Scala вы используете?

scala> nextPermutation("12354")
res0: String = 12435