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

Question

Haskell的表达能力使我们可以相对容易地定义一个幂集函数：

import Control.Monad (filterM)

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

为了能够完成我的任务，关键是需要按照特定函数对该幂集进行排序，因此我的实现看起来有点像这样：

要执行此任务，必须按照特定的函数对幂集进行排序，因此我的实现类似于以下内容：

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

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

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

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 子集，因为这样可以通过“即时生成”而大大提高性能，而不必检查所有元素。

- ThreeFx

---

对于任意的排序函数，你真的无法做得更好。寻找能够利用的排序函数中的结构。 - luqui

排序函数是什么或它有哪些特性？如果没有关于这个函数的一些知识，你将无法更好地处理 - 例如，考虑该函数是密码哈希函数。 - Petr

Answer 1

如果你想允许完全通用的排序函数，那么就不能绕过检查幂集中的所有元素。(毕竟，你怎么知道是否有一个特殊条款使得一个特定的集合[6,8,34,42]与它的邻居具有完全不同的排名？)

然而，你可以通过以下方式使算法变得更快：

1. 仅在筛选后进行排序：排序是O(n·log n)，因此你需要保持n低；对于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

基本上，让我们面对现实吧，除非基础非常小，否则任何东西的幂集都是不可行的。特定应用“在某个范围内求和”基本上是一个装箱问题；有一些相当有效的方法来做这种事情，但你必须放弃完美的通用性和量化所有一般子集的想法。

- leftaroundabout

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]）来生成幂集！虽然这个表达式很有趣，但它非常低效！）

- alias