Как работает эта перестановка (Scala)?

Question

Я смотрю на решение Павла для Project Euler, вопрос 24, но не могу понять, как работает эта функция - может кто-нибудь объяснить, что она делает?Его цель - вернуть миллионную лексикографическую перестановку цифр от 0 до 9.

def ps(s: String): Seq[String] = if(s.size == 1) Seq(s) else 
  s.flatMap(c => ps(s.filterNot(_ == c)).map(c +))

val r = ps("0123456789")(999999).toLong

Я понимаю, что когда входная строка имеет длину 1, функция возвращает этот символ в виде Seq, и я думаю, что тогдаслучается так, что он добавляется к единственному оставшемуся символу, но я не могу реально представить, как вы дойдете до этой точки или почему это приводит к списку перестановок.

(я уже решил проблемуЯ сам, но использовал метод permutations, что делает его довольно тривиальным 1-строчным, но хотел бы иметь возможность понять вышесказанное.)

Answer 1

Для каждой буквы (flatMap(c => ...)) данной строки s, ps генерирует перестановку, переставляя оставшиеся буквы ps(s.filterNot(_ == c)) и добавляя перед этой перестановкой взятую букву (map(c +)). Для тривиального случая однобуквенной строки он ничего не делает (if(s.size == 1) Seq(s)).

Редактировать : Почему это работает?

Давайте начнем с тасования строки из одной буквы:

[a]
-> a   # done.

Теперь для двух букв мы разбиваем задачу на подзадачи. Возьмите каждого персонажа в наборе, поставьте его на первую позицию и перестановите остальные.

a [b]
-> b
b [a]
-> a

Для трех букв это одно и то же. Возьмите каждый символ и добавьте его к каждой из подстановок оставшихся букв.

a [b c]
-> b [c]
   -> c
-> c [b]
   -> b
b [a c]
-> a [c]
   -> c
-> c [a]
# ... and so on

Таким образом, в основном самая внешняя функция гарантирует, что каждая буква попадает в первую позицию, первый рекурсивный вызов гарантирует то же самое для второй позиции и т. Д.

Answer 2

Давайте выпишем это в псевдокоде:

for each letter in the string
  take that letter out
  find all permutations of what remains
  stick that letter on the front

Поскольку он работает для каждой буквы в строке , то, что это эффективно делает, это перемещает каждую букву по очереди в начало строки (что означает, что первая буква может быть любой из присутствующих букв что вам нужно для перестановки). Поскольку он работает рекурсивно, остаток - это каждая оставшаяся перестановка.

Обратите внимание, что этот алгоритм предполагает, что все буквы разные (потому что filterNot используется для удаления выбранной буквы); метод перестановок в библиотеке коллекций не предполагает этого.

Answer 3

Не имеет отношения к этому, но вам может быть интересно узнать, что вы можете вычислить миллионную лексикографическую перестановку, не вычисляя ни одну из предыдущих.

Идея довольно проста: для N цифр есть N! перестановок.Это означает, что 10 цифр могут дать 3628800 перестановок, 9 цифр могут дать 362880 перестановок и так далее.Учитывая эту информацию, мы можем вычислить следующую таблицу:

First digit    First Permutation    Last Permutatation
0              1                    362880
1              362881               725760
2              725761               1088640
3              1088641              1451520
4              1451521              1814400
5              1814401              2177280
6              2177281              2540160
7              2540161              2903040
8              2903041              3265920
9              3265921              3628800

Таким образом, первая цифра будет 2, потому что это диапазон, в котором находится 1000000.Или, проще говоря, первая цифра - это цифра в индексе (1000000 - 1) / fat(9).Так что вам просто нужно применить это рекурсивно:

def fat(n: Int) = (2 to n).foldLeft(1)(_*_)
def permN(digits: String, n: Int): String = if (digits.isEmpty) "" else {
    val permsPerDigit = fat(digits.length - 1)
    val index = (n - 1) / permsPerDigit
    val firstDigit = digits(index)
    val remainder = digits filterNot (firstDigit ==)
    firstDigit + permN(remainder, n - index * permsPerDigit)
}