Haskell 功能非常有限的排列

Question

我必须在 haskell 中实现一个函数，它接受一个列表 [Int] 并给出一个包含所有排列的列表 [[Int]]，但我只被允许使用： []、:、True、False、比较、&&、|| 和 not

permutations [] = [[]]
permutations xs = [(y:zs) | (y,ys) <- picks xs, zs <- permutations ys]
   where
   picks (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- picks xs]

我的想法是使用类似的东西，但我必须更换 <-

Answer 1

正如 chepner 在评论中提到的，一些缺失的基本库函数可以很容易地“当场”重新实现。

Wikipedia article on permutations leads us to, among many other things, the Steinhaus–Johnson–Trotter algorithm，好像很适合链表。

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

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

例如，表达式 spread 4 [1,2,3] 必须将 4 放在 [1,2;3] 内所有可能的位置，因此计算结果为：[[4,1,2,3],[1,4,2,3],[1,2,4,3],[1,2,3,4]]。要获得 [1,2,3,4] 的所有排列，您只需将 spread 4 应用于 [1,2,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))

总的来说，符合规则的源代码版本应该是这样的，它有自己的 map 和 concat Prelude 函数的本地版本：

permutations :: [a] -> [[a]]
permutations  []     =  [[]]
permutations (x:xs)  =  myConcat (myMap (spread x) (permutations xs))
  where
    myMap fn  []     =  []
    myMap fn (z:zs)  =  (fn z) : (myMap fn zs)

    myConcat   []          =  []
    myConcat ([]:zss)      =  myConcat zss
    myConcat ((z:zs):zss)  =  z : (myConcat (zs:zss))

    spread z []      =  [[z]]
    spread z (y:ys)  =  ( z:y:ys) : (myMap (y:) (spread z ys))

Haskell 功能非常有限的排列

Haskell Permutations with very limited functions

haskell

permutation

whitelist