Получите перестановки в лексикографическом порядке с помощью Haskell

Я работаю над проблемой 24 из Project Euler, которая выглядит следующим образом:

Перестановка - это упорядоченное расположение объектов. Например, 3124 - это одна из возможных перестановок цифр 1, 2, 3 и 4. Если все перестановки перечислены в числовом или алфавитном порядке, мы называем это лексикографическим порядком. Лексикографические перестановки 0, 1 и 2:

012 021 102 120 201 210

Какая миллионная лексикографическая перестановка цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9?

Я пытаюсь решить эту проблему с помощью Haskell и начал с подхода грубой силы:

import Data.List
(sort . permutation) [0..9] !! 999999

Но это занимает слишком много времени, и мне интересно, не потому ли, что программа сначала получает все перестановки, затем сортирует их все, а затем, наконец, берет миллионный элемент, что намного больше, чем нужно.

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

Алгоритм, который я имею в виду, состоит в том, чтобы сначала отсортировать входной список x, затем взять первый (самый маленький) элемент и добавить его к перестановкам остальных элементов в лексикографическом порядке. Эти упорядочения могут быть найдены путем рекурсивного вызова исходной функции на уже отсортированном хвосте x (что означает, что наша исходная функция должна иметь способ отмечать, отсортирован ли список ввода). Затем мы переходим к следующему по величине элементу x и так далее, пока не получим полный упорядоченный список. К сожалению, я все еще новичок в Haskell, и мои попытки написать эту функцию не увенчались успехом. Есть какие-нибудь намеки на то, как это можно сделать?


recursion sorting haskell lexicographic
person dsaxton    schedule 06.04.2017    source источник

Ответы (1)


arrow_upward
3
arrow_downward

У меня есть мысль, которая слишком длинна для комментария, но не является рабочим решением в целом. Тем не менее, это план, который должен сработать почти мгновенно.

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

Как бы то ни было, это стандартный недетерминированный алгоритм перестановки на основе select, который вы часто найдете в учебных материалах Haskell, если список ввода отсортирован в порядке возрастания. Это не алгоритм, используемый Data.List.permutations, который разработан, чтобы быть более быстрым и продуктивным с бесконечным вводом.

Но вы можете сделать лучше, чем это. Вам не нужно генерировать все перестановки перед целевой. Вы можете пропустить вперед, и это окажется очень легко.

Все, что вам нужно сделать, это посмотреть на количество перестановок, на которые вы нацелены, назовем его k и используем его для индексации перестановок. Если входные данные отсортированы лексикографически, первым элементом результата будет элемент с индексом q, за которым следует перестановка остальных элементов с индексом r, заданным (q, r) = divMod k (fact(n - 1)).

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

person Carl    schedule 06.04.2017
comment
Очень хорошая идея. Я попробую подумать, как эта функция могла бы выглядеть в Haskell. - person dsaxton; 06.04.2017