Более быстрый способ генерации комбинаций с заданной длиной, сохраняя порядок

Question

TL; DR : я хочу точное поведение как filter ((== 4) . length) . subsequences. Простое использование subsequences также создает списки переменной длины, на обработку которых уходит много времени. Поскольку в конце нужны только списки длины 4, я подумал, что должен быть более быстрый путь.

---

У меня есть список функций. Список имеет тип [Wor -> Wor]

Список выглядит примерно так

[f1, f2, f3 .. fn]

Мне нужен список списков функций n с сохранением порядка, подобного этому

ввод: [f1, f2, f3 .. fn]

аргумент: 4 функции

output: список из 4 функций.

Ожидаемый результат будет в том случае, если в подсписке есть f1, он всегда будет в head списка.

Если в подсписке есть f2 и если в подсписке нет f1, f2 будет в head. Если fn находится в подсписке, оно будет на last.

В общем, если в списке есть fx, оно никогда не будет перед f(x - 1).

В основном сохранение порядка основного списка при создании подсписков.

Можно предположить, что длина списка всегда будет больше заданного аргумента.

Я только начинаю изучать Haskell, поэтому я не очень много пробовал, но пока что вот что я пробовал:

Генерация перестановок с функцией subsequences и применение (filter (== 4) . length) к ней, похоже, генерируют правильные перестановки - но это не сохраняет порядок - (Это сохраняет порядок, я путал его со своей собственной функцией).

Так что мне делать?

Также, если возможно, есть ли в Hackage или Stackage функция или комбинация функций, которые могут это сделать? Потому что я хотел бы понять источник.

Answer 1

Вот лучшее, что я смог придумать. Это отвечает на вызов, который Уилл Несс поставил как можно ленивее на входе. В частности, ndtake m ([1..n]++undefined) будет выдавать как можно больше записей, прежде чем выдать исключение. Кроме того, он стремится максимально увеличить общий доступ к спискам результатов (обратите внимание на обработку end в ndtakeEnding'). Это позволяет избежать проблем с плохо сбалансированным добавлением в список, используя список различий. Эта основанная на последовательности версия значительно быстрее, чем любая версия с чистым списком, которую я придумал, но я не разобрался, почему это так. У меня есть ощущение, что, возможно, можно добиться большего, лучше понимая, что происходит, но, похоже, это работает очень хорошо.

Вот общая идея. Предположим, мы просим ndtake 3 [1..5]. Сначала мы производим все результаты, заканчивающиеся на 3 (из которых есть один). Затем мы производим все результаты, заканчивающиеся на 4. Мы делаем это путем (по существу) вызова ndtake 2 [1..3] и добавления 4 к каждому результату. Мы продолжим в том же духе, пока у нас не останется больше элементов.

import qualified Data.Sequence as S
import Data.Sequence (Seq, (|>))
import Data.Foldable (toList)

Мы будем использовать следующую простую служебную функцию. Это почти то же самое, что и splitAtExactMay из «безопасного» пакета, но, надеюсь, немного проще для понимания. По причинам, которые я не исследовал, разрешение этого результата при отрицательном аргументе приводит к ndtake с отрицательным аргументом, эквивалентным subsequences. Если вы хотите, вы можете легко изменить ndtake на что-то другое для отрицательных аргументов.

-- to return an empty list in the negative case.
splitAtMay :: Int -> [a] -> Maybe ([a], [a])
splitAtMay n xs
  | n <= 0 = Just ([], xs)
splitAtMay _ [] = Nothing
splitAtMay n (x : xs) = flip fmap (splitAtMay (n - 1) xs) $
  \(front, rear) -> (x : front, rear)

Теперь мы действительно начали. ndtake реализован с использованием ndtakeEnding, который создает своего рода «список различий», позволяющий дешево объединять все частичные результаты.

ndtake :: Int -> [t] -> [[t]]
ndtake n xs = ndtakeEnding n xs []

ndtakeEnding :: Int -> [t] -> ([[t]] -> [[t]])
ndtakeEnding 0 _xs = ([]:)
ndtakeEnding n xs = case splitAtMay n xs of
    Nothing -> id -- Not enough elements
    Just (front, rear) ->
        (front :) . go rear (S.fromList front)
  where
    -- For each element, produce a list of all combinations
    -- *ending* with that element.
    go [] _front = id
    go (r : rs) front =
      ndtakeEnding' [r] (n - 1) front
        . go rs (front |> r)

ndtakeEnding не вызывает себя рекурсивно. Скорее, он вызывает ndtakeEnding' для расчета комбинаций передней части. ndtakeEnding' очень похоже на ndtakeEnding, но с некоторыми отличиями:

1. Мы используем Seq вместо списка для представления входной последовательности. Это позволяет нам дешево расколоться и подхватывать, но я пока не уверен, почему это дает амортизированную производительность, которая в этом случае намного лучше.
2. Мы уже знаем, что входная последовательность достаточно длинная, поэтому нам не нужно проверять.
3. Нам передали хвост (end), чтобы добавить к каждому результату. Это позволяет нам делиться хвостами, когда это возможно. Существует множество возможностей для обмена хвостами, поэтому можно ожидать, что это будет существенной оптимизацией.
4. Мы используем foldr вместо сопоставления с образцом. Выполнение этого вручную с сопоставлением с образцом дает более четкий код, но худшие постоянные факторы. Это связано с тем, что шаблоны :<| и :|>, экспортированные из Data.Sequence, являются нетривиальными синонимами шаблонов, которые выполняют небольшие вычисления, включая распределение амортизированного O (1), для построения хвостового или начального сегмента, тогда как не нужно их строить.

Примечание: эта реализация ndtakeEnding' хорошо работает для последних GHC и контейнеров; это кажется менее эффективным для более ранних версий. Это может быть работа Доннахи Почки на foldr для Data.Sequence. В более ранних версиях было бы более эффективно вручную сопоставлять шаблоны, используя viewl для версий, которые не предлагают синонимов шаблонов.

ndtakeEnding' :: [t] -> Int -> Seq t -> ([[t]] -> [[t]])
ndtakeEnding' end 0 _xs = (end:)
ndtakeEnding' end n xs = case S.splitAt n xs of
     (front, rear) ->
        ((toList front ++ end) :) . go rear front
  where
    go = foldr go' (const id) where
      go' r k !front = ndtakeEnding' (r : end) (n - 1) front . k (front |> r)
    -- With patterns, a bit less efficiently:
    -- go Empty _front = id
    -- go (r :<| rs) !front =
    --  ndtakeEnding' (r : end) (n - 1) front
    --    . go rs (front :|> r)

Answer 2

Вы описываете недетерминированный take:

ndtake :: Int -> [a] -> [[a]]
ndtake 0 _      = [[]]
ndtake n []     = []
ndtake n (x:xs) = map (x:) (ndtake (n-1) xs) ++ ndtake n xs

Либо мы берем x, и имеем n-1 больше, чтобы взять от xs; или мы не берем x и не имеем n дополнительных элементов, которые можно взять из xs.

Продолжительность:

> ndtake 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

---

Обновление: вы хотели эффективности. Если мы уверены, что список ввода конечен, мы можем стремиться остановить как можно скорее:

ndetake n xs = go (length xs) n xs
    where
    go spare n _  | n >  spare = []
    go spare n xs | n == spare = [xs]
    go spare 0 _      =  [[]]
    go spare n []     =  []
    go spare n (x:xs) =  map (x:) (go (spare-1) (n-1) xs) 
                            ++     go (spare-1)  n   xs

Попытка:

> length $ ndetake 443 [1..444]
444

Первая версия, кажется, застряла на этом входе, но последняя возвращается немедленно.

---

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

ndzetake :: Int -> [a] -> [[a]]
ndzetake n xs | n > 0 = 
    go n (length (take n xs) == n) (drop n xs) xs
    where
    go n b p ~(x:xs)
         | n == 0 = [[]]
         | not b  = []
         | null p = [(x:xs)]
         | otherwise = map (x:) (go (n-1) b p xs)
                          ++ go n b (tail p) xs

Теперь последний тест также работает мгновенно с этим кодом.

Здесь еще есть возможности для улучшения. Как и с библиотечной функцией subsequences, пространство поиска можно исследовать еще более лениво. Прямо сейчас у нас есть

> take 9 $ ndzetake 3 [1..]
[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,2,11]]

, но он может найти [2,3,4], прежде чем вытолкнуть 5 из списка ввода. Должны ли мы оставить это как упражнение?