Directly generate specific subsets of a force set?

Question

The Haskell expression allows us to fairly easily define the poweret function:

import Control.Monad (filterM) powerset :: [a] -> [[a]] powerset = filterM (const [True, False]) 

In order to be able to perform my task, it is important that the mentioned set of permissions be sorted by a specific function, so my kind of implementation looks like this:

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

Now my question is whether there is a way to generate a subset for the parameter set given by the specific start and end point, where f(start) < f(end) and |start| < |end| |start| < |end| . For example, my parameter is a list of integers ( [1,2,3,4,5] ), and they are sorted by their sum. Now I want to extract only subsets in a given range, say 3 to 7 . One way to achieve this would be to: filter set of privileges to include only my range, but this seems (and) ineffective when working with larger subsets:

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

badFunction 3 7 sum [1,2,3,4,5] produces [[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]] .

My question now is whether there is a way to generate this list directly, without having to generate all 2^n subsets in the first place, since it will significantly improve performance by not checking all the elements, but rather by generating them on the fly. "

Answer 1

If you want to enable completely general ordering functions, then there can be no way to check all the elements of a force set. (In the end, how would you know that this is not a special offer built in that, let's say, a specific set of [6,8,34,42] completely different ratings from its neighbors?)

However, you could make the algorithm much faster

• Only sorting after filtering: sorting is O (n & logdot; log n), so you want to keep n lower here; for the filtering stage O (n) this is of less importance. (In general, the number of elements does not change when sorting.)
• Apply an order-function only once for each subset.

So,

 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 

In principle, let them face this, nothing but a very small basis is impossible. The specific application of the “amount in a certain range” is largely a problem; There are quite effective ways to do such things, but you will have to give up the idea of ​​perfect generality and quantifying common subsets.

Answer 2

Since your problem is essentially a constraint restriction problem, using an alternative SMT solution might be a better alternative here; assuming that you can provide additional IO in type and the need to install such a solver. The SBV library allows you to create such problems. Here is one encoding:

 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] 

We get:

 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]] 

For large lists, this method will beat, generating all subsets and filtering; assuming that the cost function creates reasonable constraints. (Addition will usually be OK; if you have multiplications, the solver will be more difficult.)

(As a side note, you should never use filterM (const [True, False]) to generate power packs to begin with! Although this expression is cute and fun, it is extremely inefficient!)