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的子集的快速獲取

回答

相關問題