Haskell中不使用Data.Set的列表置换

Question

我必须编写一个Haskell函数，该函数给出给定列表的所有可能排列。

类型签名必须是：

permutations :: [a] -> [[a]]

例如，一个可接受的结果是(在ghci下(：

λ>
λ> permutations [1,2,3]
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
λ> 

以下限制适用：

1. 纯列表是唯一授权的数据结构，因此没有Set或Vector
2. 排列可以以任何顺序产生
3. 该函数必须适用于任何元素类型，即没有Ord a或Eq a实例
4. 只能使用标准前奏曲中的库函数

有人知道我该怎么做吗？

Answer 1

有几种方法可以解决这个问题。jpmarinier在评论中提出了一种可能的方法，但我认为在Haskell中，遵循输入列表结构的递归方法更自然。

对于这种递归方法，你必须实现在列表为空的情况下需要发生的事情，以及在列表至少包含一个元素的情况下应该发生的事情。在这种情况下，你也可以在列表的其余部分递归使用该函数。一般结构为：

permutations [] = _
permutations (x:xs) = let xs' = permutations xs in _

空列表的情况非常简单，但有一些不同的选择会让编译器感到高兴，所以可能不太清楚应该选择哪一个。

对于至少有一个元素的情况，我将使用名为splits :: [Int] -> [([Int],[Int])]的第二个辅助函数，该函数将输入列表的所有可能的拆分计算为两个列表。

这里有一个输入和输出的例子，可以更清楚地说明我的意思：

splits [1,2,3] == [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]

该函数的实现也是递归的，并遵循相同的模式：

splits [] = _
splits (x:xs) = let xs' = splits xs in _

Answer 2

维基百科上关于排列的文章让我们想到了Steinhaus–Johnson–Trotter算法，它似乎非常适合链表。

对于这个算法，一个重要的构建块是一个我们可以声明为：的函数

spread :: a -> [a] -> [[a]]

例如，表达式spread 4 [1,2,3]必须在[1，2；3]内的所有可能位置放置4，因此计算为：[[4,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]]。要获得[1，2，4]的所有排列，您只需要将spread 4应用于[1，3，3]的所有排列。并且以递归方式编写spread很容易：

spread :: a -> [a] -> [[a]]
spread x [] = [[x]]
spread x (y:ys) = (x:y:ys) : (map (y:) (spread x ys))

因此可以得到这样的排列：

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (x:xs) = concat (map (spread x) (permutations xs))