直接生成powerset的特定子集？

Question

Haskell的表现力使我们能够轻松定义一个powerset函数:

import Control.Monad (filterM)

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

为了能够执行我的任务,所述powerset按特定函数排序是至关重要的,所以我的实现类似于:

import Data.List (sortBy)
import Data.Ord (comparing)

powersetBy :: Ord b => ([a] -> b) -> [a] -> [[a]]
powersetBy f = sortBy (comparing f) . powerset

现在我的问题是,是否有一种方法只能在给定特定点和点的情况下生成powerset 的子集,其中和.例如,我的参数是一个整数列表(),它们按总和排序.现在我想提取只能在给定范围内的子集,可以说对.实现这一目标的一种方法是使powerset仅包括我的范围,但在处理更大的子集时这似乎(并且)无效:startendf(start) < f(end)|start| < |end|[1,2,3,4,5]37filter

badFunction :: Ord b => b -> b -> ([a] -> b) -> [a] -> [[a]]
badFunction start end f = filter (\x -> f x >= start && f x <= end) . powersetBy f

badFunction 3 7 sum [1,2,3,4,5]生产[[1,2],[3],[1,3],[4],[1,4],[2,3],[5],[1,2,3],[1,5],[2,4],[1,2,4],[2,5],[3,4]].

现在我的问题是是否有一种直接生成此列表的方法,而不必首先生成所有2^n子集,因为它不会检查所有元素而是"动态"生成它们将大大提高性能.

Answer 1

如果你想允许完全通用的排序函数,那么就无法检查powerset的所有元素.(毕竟,你怎么知道这不是一个特殊的条款,例如,特定的一组[6,8,34,42]与其邻居的排名完全不同？)

但是,您可以通过以下方式快速提高算法速度

1. 只有排序后过滤:排序是Ø(ñ ·日志ñ),所以你要保持ñ低位置; 对于O(n)过滤步骤,它更重要.(无论如何,元素的数量不会因排序而改变.)
2. 仅对每个子集应用一次排序功能.

所以

import Control.Arrow ((&&&))

lessBadFunction :: Ord b => (b,b) -> ([a]->b) -> [a] -> [[a]]
lessBadFunction (start,end) f
     = map snd . sortBy (comparing fst)
               . filter (\(k,_) -> k>=start && k<=end)
               . map (f &&& id)
               . powerset

基本上,让我们面对现实,除了非常小的基础之外的任何东西都是不可行的.特定应用"总和在一定范围内"几乎是一个包装问题 ; 有很多有效的方法来做这种事情,但你必须放弃完美的通用性和量化的概念而不是一般的子集.