在Haskell中快速获得大小为N的所有子集

Question

以下(非最佳)代码为特定子集生成大小为N的所有子集.

这段代码有效,但正如我所说,这是非常不理想的.使用中间列表来避免Set.insert的O(log(n))似乎没有帮助,因为后来将列表重新转换为Set的成本很高

任何人都可以建议如何优化代码？

import qualified Data.Set as Set


subsetsOfSizeN :: Ord a => Int -> Set.Set a -> Set.Set (Set.Set a)
subsetsOfSizeN n s
  | Set.size s < n || n < 0 = error "subsetOfSizeN: wrong parameters"
  | otherwise = doSubsetsOfSizeN n s
 where doSubsetsOfSizeN n s
        | n == 0 = Set.singleton Set.empty
        | Set.size s == n = Set.singleton s
        | otherwise =
           case Set.minView s of
             Nothing -> Set.empty
             Just (firstS, restS) ->
               let partialN n = doSubsetsOfSizeN n restS in
               Set.map (Set.insert firstS) (partialN (n-1)) `Set.union` partialN n

Answer 1

这是受Pascal三角形的启发.

choose :: [b] -> Int -> [[b]]
_      `choose` 0       = [[]]
[]     `choose` _       =  []
(x:xs) `choose` k       =  (x:) `fmap` (xs `choose` (k-1)) ++ xs `choose` k

Answer 2

这段代码有效,但正如我所说,这是非常不理想的.

对我来说似乎并不那么糟糕.大小的子集的数量k设置大小的n是n `choose` k其增长相当快k ~ n/2.因此,创建所有子集必须严重缩放.

使用中间表,以避免O(log(n))中Set.insert似乎并没有帮助,因为以后再转换列表的设置巨大的成本.

嗯,我发现使用列表可以提供更好的性能.我认为,这不是渐近的,而是一个不可忽略的或多或少的常数因素.

但首先,代码中的效率低下很容易修复:

Set.map (Set.insert firstS) (partialN (n-1))

请注意,Set.map必须从头开始重建树.但我们知道它firstS总是小于任何集合中的任何元素partialN (n-1),因此我们可以使用Set.mapMonotonic它可以重用集合的脊柱.

而这个原则也是使列表具有吸引力的原因,子集是按字典顺序生成的,因此Set.fromList我们可以使用更高效的列表Set.fromDistinctAscList.转录算法产生

onlyLists :: Ord a => Int -> Set.Set a -> Set.Set (Set.Set a)
onlyLists n s
    | n == 0                    = Set.singleton Set.empty
    | Set.size s < n || n < 0   = error "onlyLists: out of range n"
    | Set.size s == n           = Set.singleton s
    | otherwise                 = Set.fromDistinctAscList . map Set.fromDistinctAscList $
                                                         go n (Set.size s) (Set.toList s)
      where
        go 1 _ xs = map return xs
        go k l (x:xs)
            | k == l = [x:xs]
            | otherwise = map (x:) (go (k-1) (l-1) xs) ++ go k (l-1) xs

在我运行的几个基准测试中,使用Sets 的修正算法比1.5更快.

反过来,在我的标准基准测试中,这几乎是dave4420的两倍.