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

以下（非最佳）代码为特定子集生成大小为N的所有子集。Haskell中所有大小为N的子集的快速获取

此代码有效，但正如我所说的，它非常不理想。使用中间列表来避免Set.insert的O（log（n））似乎没有帮助，因为之后将列表重新转换为集合的代价很大。设置

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

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

来源

2013-01-10 fons

此代码的工作，但是，正如我所说的，是高度unoptimal。

对我来说这似乎不是非常糟糕。一组大小为n的大小为k的子集的数量为n `choose` k，其对于k ~ n/2增长得相当快。因此创建所有子集必须严格缩放。

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

嗯，我发现使用列表来提供更好的性能。我认为，不是渐近的，而是一个不可忽略的或多或少的常数因子。

但首先，有一个在您的代码中的低效率是简单的修理：

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

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

而且这个原则也是使列表更具吸引力的原因，子集按照字典顺序生成，所以我们可以使用效率更高的Set.fromDistinctAscList来代替Set.fromList。转录算法收率

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

这在几个基准我已经运行比使用Set S中的修正算法快1.5和2之间×。

而这反过来，在我的标准基准，几乎快一倍dave4420的。

来源

2013-01-10 23:16:01

首先，使用更好的算法。

看看你的最后一行：

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

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

输入一个更好的算法。

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-10 22:53:47 dave4420

我发现这一点，可能是它可以帮助你

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-10 23:15:07 zurgl

是否有'（:) [U] L''而不仅仅是'[U]一个特别的原因：L''？（同样，在'l''的定义中'（++）'和'（：）'）。 – huon

是的，我更喜欢使用这种形式，因为我可以在where子句中写cons = uncurry ），concat = uncurry（++），并在cons [u] l替换[u]：l'后。 – zurgl

这是由帕斯卡三角启发。

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

来源

2013-01-11 20:24:52 rickythesk8r

很不错，我很喜欢这个 – zurgl

很优雅，恭喜:) – miniBill

subsets :: Int -> [a] -> [[a]] 
subsets 0 _ = [[]] 
subsets _ [] = [] 
subsets k (x:xs) = map (x:) (subsets (k - 1) xs) ++ subsets k xs

来源

2015-01-07 13:15:46 schickling

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

回答

相关问题