Получить все перестановки списка в Haskell

Question

Я пытаюсь сделать это с нуля, без использования библиотеки за пределами стандартной библиотеки. Heres мой код:

permutations :: [a] -> [[a]] 
permutations (x:xs) = [x] : permutations' xs 
    where permutations' (x:xs) = (:) <$> [x] <*> split xs 
      split l = [[x] | x <- l] 

Проблема заключается в том, что это производит только одну вилки недетерминистических вычислений. В идеале я бы хотел

(:) <$> [x] <*> ((:) <$> [x] <*> ((:) <$> [x] <*> ((:) <$> [x] <*> xs))) 

Но я не могу найти способ сделать это чисто. Мой желаемый результат примерно такой:

permutations "abc" -> ["abc", "acb", "bac", "bca", "cab", "cba"] 

Как это сделать?

Answer 1

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

Answer 2

Для простой реализации без учета дупликации на входе

permutations :: Eq a => [a] -> [[a]] 
permutations [] = [[]] 
permutations as = do a <- as 
        let l = delete a as 
        ls <- permutations l 
        return $ a : ls 

Тест:

λ> permutations [1,2,3] 
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 
λ> permutations "abc" 
["abc","acb","bac","bca","cab","cba"] 
λ> 

Algorithm Reference

Answer 3

Все лучше с монад:

perm :: [a] -> [[a]] 
perm []  = return [] 
perm (x:xs) = (perm xs) >>= (ins x) 
    where 
    ins :: a -> [a] -> [[a]] 
    ins x []  = [[x]] 
    ins x (y:ys) = [x:y:ys] ++ (map (y:) (ins x ys)) 

Итак: у вас есть функция, которая вставляет букву в слово, но она производит более одного слова, поэтому как применить ее рекурсивно? >>= помогает!

Answer 4

Я хотел бы сделать это следующим образом:

select :: [a] -> [(a,[a])] 
select = select' id where 
    select' _ [] = [] 
    select' acc (a:r) = (a, acc r) : select' (acc . (a:)) r 

permutations [] = [[]] 
permutations l = do 
    (a,r1) <- select l 
    r2 <- permutations r1 
    return (a: r2) 

Answer 5

Я относительно новым для Haskell, но I had developed a very efficient permutations algorithm for JS. Он почти превосходит алгоритм куч, но в JS вращение массива более дорогостоящее по сравнению с ленивой функцией Haskell iterate над списками. Таким образом, этот, в отличие от всех приведенных ответов выше, кажется, намного эффективнее.

Построен в Data.List.permutations по-прежнему в 2 раза быстрее, чем этот на сегодняшний день, так как я вообще не знаю ограничений производительности Haskell. Может быть, кто-то здесь может помочь мне немного продвинуть этот код.

Итак, у меня есть вспомогательная функция, которая возвращает список всех поворотов предоставленного списка. Такие, как

rotations [1,2,3] даст [[1,2,3],[2,3,1],[3,1,2]]

соответственно функция перманент является;

rotations :: [a] -> [[a]] 
rotations xs = take (length xs) (iterate (\(y:ys) -> ys ++ [y]) xs) 

perms :: [a] -> [[a]] 
perms []  = [[]] 
perms (x:xs) = concatMap (rotations.(x:)) (perms xs) 

Edit: Так я думал о том, как сделать этот код более эффективным. ОК списки в Haskell являются связанными списками, и в отличие от JavaScript длина не является свойством, к которому вы можете получить доступ в O (1), но O (n). Это функция, проходящая через весь проклятый список, в основном подсчитывая все элементы в списке. Поэтому очень дорого, если использовать его повторно. Это то, что мы делаем с помощью команды take (length xs) при каждом вызове функции поворота. Мы буквально вызываем его миллионы раз, если ваш входной список похож на 10-11 единиц или больше по длине.Резка это принесет огромные сбережения. Тогда давайте не будем подсчитывать длину одинаковых списков длин над более чем, но вместо этого давайте просто предоставить его;

rotations :: Int -> [a] -> [[a]] 
rotations len xs = take len (iterate (\(y:ys) -> ys ++ [y]) xs) 

Красивые. Ну, теперь нам нужно слегка изменить нашу функцию perms соответственно;

perms :: [a] -> [[a]] 
perms []  = [[]] 
perms il@(x:xs) = concatMap ((rotations len).(x:)) (perms xs) 
        where len = length il 

так очевидно il теперь назначен я Nput л IST и len кэши его длина. Теперь это красиво и довольно интересно работает быстрее чем по умолчанию Data.List.permutations.

Пока все хорошо ... Но теперь пришло время немного обмануть и сделать его еще быстрее. Одна вещь, которую я знаю, и как я только что доказал, в CS лучшим топливом для алгоритма является кеширование. Итак, что мы ищем в кеше дальше? Мы можем легко кэшировать возвращаемые значения для входных данных, например [x], [x,y] и [x,y,z] и сохранять некоторые вычисления. Вы хотите больше скорости ..? Затем бесстыдно кэш [w,x,y,z] тоже. Давайте посмотрим на новый код в целом;

rotations :: Int -> [a] -> [[a]] 
rotations len xs = take len (iterate (\(y:ys) -> ys ++ [y]) xs) 

perms :: [a] -> [[a]] 
perms []  = [[]] 
perms [x]  = [[x]] 
perms (x:[y]) = [[x,y],[y,x]] 
perms (x:y:[z]) = [[x,y,z],[y,z,x],[z,x,y],[x,z,y],[z,y,x],[y,x,z]] 
perms il@(x:xs) = concatMap ((rotations len).(x:)) (perms xs) 
        where len = length il 

Любые идеи приветствуются ...

Answer 6

Может быть, вы должны использовать существующий код:

import Data.List 
permutations [1,2,3,4]