直接生成powerset的特定子集？

Haskell的表现使我们能够比较容易地定义幂函数：直接生成powerset的特定子集？

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

现在我的问题是，是否有一种方法，只生成一个子集给出了具体的start和end点幂的，其中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]]：以更大的子集打交道时实现这一目标的方法之一将是filter幂集只包括我的范围，但是这似乎（是）无效。

现在我的问题是，是否有办法直接生成此列表，而不必首先生成所有2^n子集，因为它不会检查所有元素，而是可以“动态地”生成它们，从而大大提高性能。。

来源

2015-04-03 ThreeFx

对于任意排序功能，你真的不能做得更好。在您的订购功能中查找可以利用的结构。 – luqui 2015-04-03 19:21:28

什么是排序功能或它的属性是什么？如果没有关于函数的一些知识，你就无法做得更好 - 例如将函数看作是[加密哈希函数]（http://en.wikipedia.org/wiki/Cryptographic_hash_function）。 – 2015-04-03 19:34:14

如果你想允许完全一般的排序功能，那么不能用来检查powerset的所有元素。（毕竟，你怎么知道这不是一个特殊的子句，比如说，这个特定的子集[6,8,34,42]与其邻居的排名完全不同？）

但是，您可以使算法已经大大加快

只有排序后过滤：排序是Ø（ñ＆middot;登录ñ），所以你要保持ň这里低;对于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

基本上，让我们面对现实吧，绝不是一个非常小的基础powersets是不可行的。特定应用“总和在一定范围内”几乎是一个packaging problem;有相当有效的方法来做这种事情，但是你必须放弃完美的普遍性和量化一般子集的想法。

来源

2015-04-03 19:24:33 leftaroundabout

由于您的问题本质上是一个约束满足问题，因此使用外部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])来生成启动的功率集！是可爱和有趣的，这是非常低效的！）

来源

2015-04-04 04:36:27

直接生成powerset的特定子集？

回答

相关问题