Haskell如何生成任意长度列表的所有排列？

当然可以实现处理任意长度列表的排列生成功能啦！你现在写的列表推导式虽然能搞定固定长度的情况，但确实没法适配元素数量不确定的场景——我们可以用递归思路手动实现，或者直接用标准库现成的工具，两种方式都很靠谱。

手动实现递归版本 #

我们可以用递归的核心思路：把列表中的每个元素依次作为排列的第一个元素，然后递归生成剩余元素的所有排列，最后把这个首元素拼到每个递归结果的前面。

基于元素过滤的实现（需要Eq约束） #

这个版本逻辑直白，适合元素无重复或者不在意重复排列的场景：

permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]  -- 空列表的排列只有它自己
permutations l = [ y : perm | y <- l, perm <- permutations (filter (/= y) l) ]

举个例子，当输入[1,2,3]时，会依次取1、2、3作为首元素，分别生成剩余两个元素的排列，再把首元素拼上去，最终得到所有6种排列。

基于位置拆分的实现（无Eq约束） #

如果你的列表里有重复元素，或者不想依赖Eq类型约束，可以用拆分位置的方式来实现，避免通过元素值判断：

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = [ x : restPerm | (x, rest) <- pickElements xs, restPerm <- permutations rest ]
  where
    -- 辅助函数：把列表拆成每个元素和剩余元素的元组
    pickElements [] = []
    pickElements (first:remaining) = 
        (first, remaining) : [ (elem, first:rest) | (elem, rest) <- pickElements remaining ]

这个pickElements函数会把列表拆分成所有可能的「单个元素+剩余元素」组合，比如处理[1,2,3]时会生成[(1,[2,3]), (2,[1,3]), (3,[1,2])]，再基于这些组合递归生成排列。

直接用标准库函数 #

其实Haskell的标准库早就帮我们实现好了！Data.List模块里自带了permutations函数，直接导入使用就行，它经过优化，处理效率也更高：

import Data.List (permutations)

-- 调用示例
main = print $ permutations [1,2,3]

运行这段代码就能得到你想要的所有排列，而且它能自动适配任意长度的列表，完全不用自己造轮子～

内容的提问来源于stack exchange，提问作者Jordan Sapida