0

我面临以下问题：

从初始集合[1,2,3,4]计算所有可能的子集，即[[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]

我编写了以下generate.hs正确的 Haskell 程序。

generateSets :: Eq a => [a] -> [[a]] -> [[a]] -> [[a]]
generateSets []  _  _  = []
generateSets src [] _  = let isets = growthup [] src in generateSets src iset iset
generateSets src sets rsets = if null sets' then rsets else generateSets src sets' (rsets++sets')
  where sets' = concatMap (flip growthup src) sets

growthup :: (Eq a) => [a] -> [a] -> [[a]]
growthup ps ss = map (\suf -> ps++[suf]) ss'
  where ss' = nextoccurence ps ss

nextoccurence :: (Eq a) => [a] -> [a] -> [a]
nextoccurence [] ys = ys
nextoccurence xs ys = tail ys'
  where ys' = dropWhile (/= last xs) ys

在 GHC 解释器ghci中执行它时...

ghci> generate [1,2,3,4] [] []
ghci> [[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]

一切都很好，但是对于例如 30 号的小套程序来说，程序花费的时间太长了。

我的问题是：有可能改进我的代码以便从haskell 懒惰或垃圾收集器或其他东西中获得更多？

我的代码是并行性的良好候选者吗？

感谢您的回复！

4

1 回答 1

7

集合有很多子集。事实上，一组n 个元素有2 n个子集，所以一组 30 个元素有超过十亿个子集。无论您使用哪种方法来生成它们，即使对结果进行迭代也需要很长时间。对于更大的集合，你几乎可以忘记在宇宙热寂之前经历它们。

因此，您只能在性能方面做很多事情，因为即使将算法速度提高一倍也只会让您同时处理一个更多元素的列表。对于大多数应用程序，真正的解决方案是避免首先枚举所有子集。

也就是说，有一种简单的归纳方式来思考子集，这使得定义适当的子集函数变得容易，而无需进行任何相等比较，从而解决了您的实现中的一些问题。

对于基本情况，空集有一个子集：空集。

subsets [] = [[]]

对于至少包含一个元素(x:xs)的集合，我们有包含该元素的子集和不包含该元素的子集。x我们可以通过递归调用来获得不包含的子集，subsets xs我们可以通过预先添加这些来获得其余的x。

subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)

subsequencesin的定义Data.List基于相同的原理，但以稍微优化的方式，它也以不同的顺序返回子集并更好地利用共享。然而，正如我所说，枚举长度为 30 的列表的子集无论如何都会很慢，最好的办法是尽量避免一开始就这样做。

于 2012-05-12T02:16:06.733 回答