具有补码集的快速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:你枚举集合的项目,然后你决定是否将它们放在"选择"(元组的第一项)中,或者不是(元组的第二项).通过详尽地列举这些选择,我们得到了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:)预先设置了recwith 的元组的所有第二项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)中完成,我们现在为每个原始列表构建两个列表(和一个元组).