获取Haskell中列表的所有排列

Question

我试图从头开始这样做,而不使用标准库之外的库.继承我的代码:

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

也许你应该使用现有的代码:

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

Answer 2

TL&DR 对于比 Data.List.permutations 更快的代码，跳到第二部分

第一部分

我对 Haskell 比较陌生，但我已经为 JS 开发了一种非常有效的排列算法。它几乎击败了堆算法，但在 JS 中，iterate与列表上的惰性 Haskell函数相比，旋转数组的成本更高。因此，与上面提供的所有答案不同，这个答案似乎更有效。

内置的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)

第二部分

所以我一直在思考如何让上面的代码更有效率。好的，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，它在 GHCI 中的运行速度提高了1.33 倍，在使用 -O2 编译时提高了3 倍以上。

import Data.List

perms :: [a] -> [[a]]
perms xs = run len xs
           where
           len = length xs

           rotate :: [a] -> [a]
           rotate (x:xs) = xs ++ [x]

           rotations :: Int -> [a] -> [[a]]
           rotations l xs = take l (iterate rotate xs)

           run :: Int -> [a] -> [[a]]
           run _ []      = [[]]
           run _ [x]     = [[x]]
           run n (x:xs)  = run (n-1) xs >>= rotations n . (x:)
           --run n (x:xs)  = concatMap ((rotations n).(x:)) (run (n-1) xs)

?> length $ perms [1..13]
6227020800
(302.58 secs, 1,366,730,140,472 bytes)

?> length $ permutations [1..13]
6227020800
(404.38 secs, 1,800,750,142,384 bytes)

问题是，如果您可以使rotations函数更高效，您可以获得更好的结果，唉，我已经做了一些研究，但是这个简单的代码似乎和 Haskell 中的代码一样好。

另一个重要的一点是，我相信这个算法也是可线程化的（还没有测试过）但是应该是因为如果你检查这个run n (x:xs) = concatMap ((rotations n).(x:)) (run (n-1) xs)部分你可能会注意到我们有一个map与rotations n . (x:)前一组排列的函数。这正是我认为可以产生线程的地方。

进一步的想法...... “我真的在做正确的事情吗......？”

我想我被这里的懒惰欺骗了。我相信这样做length $ perms [1..12]并没有真正强制排列来解决，而是一直工作直到它知道排列列表的长度是 12!。我的意思是包含的值可能仍然是 thunk。

所以，而不是length，我决定做像算法的最后一个排列元素any (== [11,1,7,2,10,3,8,4,12,5,9,6]) $ perms [1..12]在哪里。所以现在我想它应该评估所有 thunk 以进行股权检查，直到它到达最后一个元素以返回 a 。[11,1,7,2,10,3,8,4,12,5,9,6]permsTrue

当这样的检查perms，并permutations用自己最后的元素，在解决类似的速度（permutations是稍快）。

欢迎任何想法...

Answer 3

对于简单的实现，无需考虑输入中的重复项

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"]
?> 

算法参考

Answer 4

我认为对于其他人的建议来说，这是更短、更优雅的变体：

permutate :: (Eq a) => [a] -> [[a]]
permutate [] = [[]]
permutate l = [a:x | a <- l, x <- (permutate $ filter (\x -> x /= a) l)]

Answer 5

它已经在标准基础库中，因此无需费力。如果您确实想了解如何执行此操作，可以查看该库的源代码。