直接生成幂集的特定子集？

Question

Haskell的表现力使我们能够相当容易地定义幂集函数：

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

现在我的问题是是否有一种方法可以只生成给定特定 start 和 end 点的幂集的子集，其中 f(start) < f(end) 和 |start| < |end|。例如，我的参数是一个整数列表 ([1,2,3,4,5])，它们按总和排序。现在我只想提取给定范围内的子集，比方说 3 到 7。实现这一目标的一种方法是 filter 功率集仅包括我的范围，但这在处理较大的子集时似乎（并且）无效：

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 个子集，因为它不必检查所有元素而是生成它们，从而大大提高性能"on the fly".

Answer 1

如果您想允许完全通用的排序函数，那么不能是一种绕过检查幂集所有元素的方法。（毕竟，你怎么知道这不是一个内置的特殊子句，它给出了特定集合 [6,8,34,42] 与其邻居完全不同的排名？）

但是，您可以通过

使算法已经大大加快

只排序after过滤：排序是O (n · log n), 所以你想在这里保持 n 低;对于 O (n) 过滤步骤，它并不重要。（无论如何，元素的数量不会因排序而改变。）
对每个子集仅应用排序函数一次。

所以

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

基本上，让我们面对现实吧，除了非常小的基础之外，任何东西的幂集都是不可行的。特定应用程序“在一定范围内求和”几乎是 packaging problem；有一些非常有效的方法可以做这种事情，但是你必须放弃完美通用性和对一般子集进行量化的想法。

Answer 2

由于您的问题本质上是约束满足问题，因此使用外部 SMT 求解器可能是更好的选择；假设您可以负担得起该类型的额外 IO，并且需要安装这样的求解器。 SBV 库允许构建此类问题。这是一种编码：

import Data.SBV

-- c is the cost type
-- e is the element type
pick :: (Num e, SymWord e, SymWord c) => c -> c -> ([SBV e] -> SBV c) -> [e] -> IO [[e]]
pick begin end cost xs = do
        solutions <- allSat constraints
        return $ map extract $ extractModels solutions
  where extract ts  = [x | (t, x) <- zip ts xs, t]
        constraints = do tags <- mapM (const free_) xs
                         let tagged    = zip tags xs
                             finalCost = cost [ite t (literal x) 0 | (t, x) <- tagged]    
                         solve [finalCost .>= literal begin, finalCost .<= literal end]

test :: IO [[Integer]]
test = pick 3 7 sum [1,2,3,4,5]

我们得到：

Main> test
[[1,2],[1,3],[1,2,3],[1,4],[1,2,4],[1,5],[2,5],[2,3],[2,4],[3,4],[3],[4],[5]]

对于大型列表，此技术将胜过生成所有子集和过滤；假设成本函数产生合理的约束。（加法通常没问题，如果你有乘法，后端求解器会更难。）

（附带说明，您永远不应该使用 filterM (const [True, False]) 来生成幂集！虽然这个表达式很可爱有趣，但效率极低！）

直接生成幂集的特定子集？

Directly generating specific subsets of a powerset?

combinations

haskell

set