Generando direttamente sottoinsiemi specifici di un powerset?

Question

espressività di Haskell ci permette di definire piuttosto facilmente una funzione Powerset:

import Control.Monad (filterM) 

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

Per essere in grado di svolgere il mio compito è fondamentale per detto Powerset per essere ordinato per una specifica funzione, quindi la mia implementazione sorta di simile a questo :

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

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

Ora la mia domanda è se c'è un modo per generare solo un sottoinsieme della Powerset dato un preciso start e end punto, dove f(start) < f(end) e |start| < |end|. Ad esempio, il mio parametro è un elenco di numeri interi ([1,2,3,4,5]) e sono ordinati in base alla loro somma. Ora voglio estrarre solo i sottoinsiemi in un determinato intervallo, diciamo 3 a 7. Un modo per raggiungere questo obiettivo sarebbe quello di filter il Powerset per includere solo la mia fascia ma questo sembra (ed è) inefficace quando si tratta di sottoinsiemi più grandi:

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] produce [[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]].

Ora la mia domanda è se esiste un modo per generare direttamente questo elenco, senza dover generare tutti i sottoinsiemi 2^n, poiché migliorerà drasticamente le prestazioni non dovendo controllare tutti gli elementi ma piuttosto generarli "al volo" .

Answer 1

Se si desidera consentire funzioni di ordinamento completamente generali, quindi non è possibile essere un modo per controllare tutti gli elementi del powerset. (Dopotutto, come sapresti non è una clausola speciale incorporata che dica, per esempio, il particolare set [6,8,34,42] una classifica completamente diversa dai suoi vicini?)

Tuttavia, potresti rendere l'algoritmo già drasticamente più veloce

1. Solo di ordinamento dopo filtraggio: ordinamento è O (n & middot; accedere n), così si vuole tenere n bassa qui; per il O (n) passaggio di filtro che conta di meno. (E comunque, il numero di elementi non cambia attraverso l'ordinamento.)
2. Applicare la funzione di ordine solo una volta per ogni sottoinsieme.

Così

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 sostanza, diciamocelo, powerset di tutto tranne che una piccola base sono fattibile. La specifica applicazione “ somma in un determinato intervallo ” è praticamente un packaging problem; ci sono modi abbastanza efficienti per fare questo genere di cose, ma dovrai rinunciare all'idea di una perfetta generalità e di quantificazione su sottoinsiemi generali.

Answer 2

Poiché il problema è essenzialmente un problema di soddisfazione dei vincoli, l'utilizzo di un risolutore SMT esterno potrebbe essere l'alternativa migliore qui; partendo dal presupposto che puoi permetterti l'I/O extra nel tipo e la necessità di installare un tale risolutore. La libreria SBV consente la costruzione di tali problemi.Ecco una codifica:

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] 

otteniamo:

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

Per grandi liste, questa tecnica sarà battere generare tutti i sottoinsiemi e filtraggio; supponendo che la funzione di costo generi limiti ragionevoli. (L'aggiunta sarà in genere OK, se hai moltiplicazioni, il risolutore di backend avrà un tempo più difficile.)

(Come nota a margine, non devi mai usare filterM (const [True, False]) per generare set di potenza per iniziare! Mentre quella espressione è carino e divertente, è estremamente inefficiente!)