haskell - 带补集的快速幂集实现

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:您枚举集合中的项目，然后决定是否将它们放入“选择”(元组的第一项)或不(元组的第二项)。通过详尽地列举这些选择，我们得到了幂集。

所以我们可以做同样的事情，例如使用递归:

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)) 中完成，我们现在为每个原始列表构建两个列表(和一个元组)。