4

以下（非最优）代码为某个子集生成所有大小为 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
4

5 回答 5

14

这是受到帕斯卡三角形的启发。

choose :: [b] -> Int -> [[b]]
_      `choose` 0       = [[]]
[]     `choose` _       =  []
(x:xs) `choose` k       =  (x:) `fmap` (xs `choose` (k-1)) ++ xs `choose` k
于 2013-01-11T20:24:52.403 回答
7

该代码有效，但正如我所说，它非常不理想。

对我来说似乎并没有那么糟糕。k一组大小的大小子集的数量n增长n `choose` k得相当快k ~ n/2。因此，创建所有子集必须严重扩展。

由于稍后将列表重新转换为 Set 的成本很高，因此使用中间列表来避免O(log(n))ofSet.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 到 2 倍。

反过来，在我的标准基准测试中，速度几乎是dave4420的两倍。

于 2013-01-10T23:16:01.060 回答
1 
subsets :: Int -> [a] -> [[a]]
subsets 0 _ = [[]]
subsets _ [] = []
subsets k (x:xs) = map (x:) (subsets (k - 1) xs) ++ subsets k xs
于 2015-01-07T13:15:46.503 回答
0

首先，使用更好的算法。

看看你的最后一行：

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

评估doSubsetsOfSizeN k (Set.fromList $ 1:2:xs)将涉及评估doSubsetsOfSizeN (k-1) (Set.fromList xs) 两次（插入1时一次，插入时一次2）。这种重复是浪费的。

输入更好的算法。

mine :: Ord a => Int -> Set.Set a -> Set.Set (Set.Set a)
mine n s | Set.size s < n || n < 0 = Set.empty
         | otherwise               = Set.foldr cons nil s !! n
    where
        nil :: Ord a => [Set.Set (Set.Set a)]
        nil = Set.singleton Set.empty : repeat Set.empty
        cons :: Ord a => a -> [Set.Set (Set.Set a)] -> [Set.Set (Set.Set a)]
        cons x sets = zipWith Set.union sets
                               (Set.empty : map (Set.map $ Set.insert x) sets)

mine 9 (Data.Set.fromList [0..18]) `seq` ()比subsetsOfSizeN 9 (Data.Set.fromList [0..18]) `seq` ()并且应该有更好的渐近性能。

我还没有尝试进一步优化这个。可能还有更好的算法。

（如果成本insert和fromList是问题，您应该考虑返回一个列表列表而不是一组集合。）

于 2013-01-10T22:53:47.617 回答
0

我找到了这个，也许它可以帮助你

f []  = [[1]]
f l   = (:) [u] l'
    where 
        u  = succ (head (head l))
        l' = (++) l (map(\x->(:) u x) l)

fix f n = if (n==0) then [] else f (fix f (n-1))

测试它

$ length $ (fix f 10) => 1023 -- The empty set is always include then == 1024
于 2013-01-10T23:15:07.673 回答