列表的所有可能的子列表

Question

我需要编写一个函数来生成一个列表,其中包含列表中所有可能的子列表的列表.所以类型必须是:

partitions :: [a] -> [[[a]]]

它应该给:

分区[1..4] = [[[1],[2],[3],[4]],[[1,2],[3],[4]],[[1],[2 ,3],[4]],[[1,2,3],[4]],[[1],[2],[3,4]],[[1,2],[3,4] ]],[[1],[2,3,4]],[[1,2,3,4]]]

我认为列表理解是最好的方法.到目前为止,我有:

partitions :: [a]  -> [[[a]]]
partitions (x:xs) = foldr insert [[]] (x:xs)
   where insert ys zs = ys:x:zs

这会引发您所期望的类型错误,但我不知道如何解决它.我觉得我错过了一些明显的东西,任何帮助都会受到赞赏.

Answer 1

我会从直接递归开始.分解一下,对于较长列表中的第一个元素有什么可能性？

1. 它可以是其中一个分区列表的唯一元素.
2. 它可以是具有多个元素的分区列表的一部分.

从您的示例中,您似乎希望保持原始元素的顺序,因此每个分区的成员只能是连续的子列表,这使得它更容易一些.

所以我们可以开始了

partitions :: [a] -> [[[a]]]
partitions [] = [[]]    -- only one partition of an empty list, an empty partition
partitions (x:xs) = [[x]:part | part <- partitions xs] ++ [(x:ys):yss | (ys:yss) <- partitions xs]

产量

*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1],[2],[3,4]],[[1],[2,3],[4]],[[1],[2,3,4]],[[1,2],[3],[4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4]]]

不是所需的顺序.如果重要,我们必须重写.所需的顺序列出了直接连续的第一个元素的两种选择,因此我们可以编写它

partitions (x:xs) = partitions xs >>= \zs -> case zs of
                                               [] -> [[[x]]]
                                               (ys:yss) -> [[x]:ys:yss, (x:ys):yss]

我们需要明确区分空分区(在递归结束时)和非空分区的情况,在上面这是通过绑定到模式隐式完成的(ys:yss).这产生了所需的顺序

*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1,2],[3],[4]],[[1],[2,3],[4]],[[1,2,3],[4]],[[1],[2],[3,4]],[[1,2],[3,4]],[[1],[2,3,4]],[[1,2,3,4]]]

使用(>>=)列表monad 的绑定的事实是flip concatMap版本

partitions (x:xs) = concatMap insert (partitions xs)
  where
    insert [] = [[[x]]]
    insert (ys:yss) = [[x]:ys:yss, (x:ys):yss]

可能更具可读性.