haskell - 具有补充集的快速Powerset实现

我想要一个功能

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]

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

最佳答案

好吧，您应该看到这样的幂集:您枚举集合中的项，然后决定是否将它们放入“选择”(元组的第一项)，或者不放入“选择”中(元组的第二项)。通过详尽地列举这些选择，我们得到了幂集。

因此，我们可以执行相同的操作，例如使用递归:

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