用补码集快速实现powerset

Question

我想有个活动

powersetWithComplements :: [a] -> [([a], [a])]

例如：

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

很容易获得一些实现，例如

powerset :: [a] -> [[a]]
powerset = filterM (const [False, True])

powersetWithComplements s = let p = powerset s in zip p (reverse p)

或

powersetWithComplements s = [ (x, s \\ x) | x <- powerset s]

但我估计这两种方法的表现都会很差。什么是最佳方法？可以使用与[]列表不同的数据结构。

Answer 1

那么，您应该看到这样一个powerset :您对集合的项进行枚举，然后决定是否将这些项放在“set”(元组的第一项)中，或者不放在(元组的第二项)中。通过详尽地列举这些选择，我们得到了powerset。

因此，我们也可以这样做，例如使用递归：

import Control.Arrow(first, second)

powersetWithComplements [] = [([],[])]
powersetWithComplements (x:xs) = map (second (x:)) rec ++ map (first (x:)) rec
    where rec = powersetWithComplements xs

因此，在这里，map (second (x:)用x为rec的第二个元组的所有第二项加上x，而map (second (x:)对rec的第一个元组的第一项做同样的操作。其中rec是项尾部的递归。

Prelude Control.Arrow> powersetWithComplements [1,2,3]
[([],[1,2,3]),([3],[1,2]),([2],[1,3]),([2,3],[1]),([1],[2,3]),([1,3],[2]),([1,2],[3]),([1,2,3],[])]

这种方法的优点是，我们不为生成的每个列表生成一个补充列表:我们同时构建选择和补充。此外，我们可以重用我们在递归中构建的列表，这将减少内存占用。

在时间复杂度和内存复杂度方面，powersetWithComplements函数都是相等的(当然，就处理时间而言，这是复杂性，因为我们需要更多的时间，因为我们需要额外的工作量)，因为列表的前置通常是在O(1)中完成的，现在我们为每个原始列表构建两个列表(和一个元组)。

Answer 2

由于您正在寻找一个“快速”实现，我想我将与Willem的解决方案共享一些基准实验。

我认为使用DList代替普通列表将是一个很大的改进，因为DLists有固定的时间附加，而附加列表与左参数的大小成线性关系。

psetDL :: [a] -> [([a],[a])]
psetDL = toList . go
    where
    go [] = DList.singleton ([],[])
    go (x:xs) = (second (x:) <$> rec) <> (first (x:) <$> rec)
        where
        rec = go xs

但这并没有产生显著的影响。

我怀疑这是因为我们正在遍历这两个子列表，因为fmap (<$>)。我们可以通过执行类似于CPS的操作来避免遍历--转换函数，将累积的集合作为参数传递，而不是返回它们。

psetTail :: [a] -> [([a],[a])]
psetTail = go [] []
    where
    go a b [] = [(a,b)]
    go a b (x:xs) = go a (x:b) xs <> go (x:a) b xs

这对大小为20的列表产生了220%的改进。现在，由于我们没有从from遍历列表，所以可以使用DList来消除附加遍历：

psetTailDL :: [a] -> [([a],[a])]
psetTailDL = toList . go [] []
    where
    go a b [] = DList.singleton (a,b)
    go a b (x:xs) = go a (x:b) xs <> go (x:a) b xs

这带来了额外的20%的改善。

Answer 3

我想最好的灵感来自于你的reverse发现

partitions s=filterM(const[False,True])s
        `zip`filterM(const[True,False])s

而不是一朵很有可能的花

partitions[]=[([],[])]
partitions(x:xs)=[p|(f,t)<-partitions xs,p<-[(l,x:r),(x:l,r)]]

或者是一个时空高效的有限列表索引器。

import Data.Array
import Data.Bits
import Data.List
partitions s=[(map(a!)f,map(a!)t)
             |n<-[length s],a<-[listArray(0,n-1)s],
              m<-[0..2^n-1],(f,t)<-[partition(testBit m)[0..n-1]]]