通过补码集实现快速功率组

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

好吧，你应该看到这样的幂集：你枚举集合的项目，你决定是否将它们放在"选择"(元组的第一项)中(元组的第一项)。通过详尽地枚举这些选择，我们得到了幂集。

因此，我们可以做同样的事情，例如使用递归：

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

所以这里map (second (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函数将相等(请注意，这是复杂性，当然就处理时间而言，它将需要更多的时间，因为我们做了额外的工作)，就像powerset函数一样，因为预置列表通常是在O(1)中完成的)，我们现在为每个原始列表构建两个列表(和一个元组)。

Answer 2

由于您正在寻找"快速"实现，我想我会分享一些我使用 William 解决方案所做的基准实验。

我认为使用 DList而不是普通列表将是一个很大的改进，因为 DList 具有常量时间追加，而附加列表在左参数的大小上是线性的。

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% 的改进。 现在，由于我们没有从 fmapping 遍历列表，我们可以通过使用 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]]]