列表的所有可能子列表 [英] All possible sublists of a list

问题描述

我需要编写一个函数，该函数生成一个包含列表的所有可能子列表的列表的列表.因此类型必须为:

I need to write a function that generates a list containing lists of all the possible sublists of a list. So the type must be:

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]]] p

partitions [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]]]

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

I'm thinking a list comprehension is the best way to go. So far I have:

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

这会引发您所期望的类型错误，但是我不知道如何解决它.我觉得我缺少明显的东西，任何帮助将不胜感激.

This throws up type errors as you would expect, but I don't know how to fix it. I feel I'm missing something obvious, any help would be appreciated.

推荐答案

我将从直接递归开始.分解一下，较长列表中的第一个元素有什么可能性?

I would start with a direct recursion. Break it down, what possibilities are there for the first element in a longer list?

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

在您的示例中，您似乎希望保持原始元素的顺序，因此每个分区的成员只能是连续的子列表，这使操作起来更加容易.

From your example, it seems you want to keep the original elements in order, so the members of each partition can only be contiguous sublists, which makes it somewhat easier.

所以我们可以开始

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

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

not the desired order. If that matters, we have to rewrite. The desired order lists both choices for the first element in direct succession, so we could write it

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

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

where we need to explicitly distinguish between the cases of an empty partition (at the end of the recursion) and nonempty partitions, which in the above was done implicitly by binding to the pattern (ys:yss). That yields the desired order

*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的事实

Using the fact that the bind (>>=) for the list monad is flip concatMap, the version

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

可能更具可读性.

这篇关于列表的所有可能子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！