Bezpośrednie generowanie określonych podzbiorów zestawu?

Question

wyrazistość Haskell'a pozwala nam dość łatwo zdefiniować funkcję PowerSet:

import Control.Monad (filterM) 

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

aby móc wykonać swoje zadanie to ma zasadnicze znaczenie dla wspomnianej PowerSet być klasyfikowane według określonej funkcji, więc moja realizacja rodzaj wygląda następująco :

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

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

teraz moje pytanie brzmi, czy istnieje sposób, aby wygenerować tylko podzbiór z PowerSet danego konkretnego start i end punkt, gdzie f(start) < f(end) i |start| < |end|. Na przykład, moim parametrem jest lista liczb całkowitych ([1,2,3,4,5]) i są one sortowane według ich sum. Teraz chcę wyodrębnić tylko podzbiory w danym zakresie, powiedzmy 3 do 7. Jednym ze sposobów osiągnięcia tego celu byłoby filter PowerSet tylko to moim przedziale, ale to wydaje się (i jest) nieskuteczny gdy ma do czynienia z większymi podzbiory:

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

Teraz moje pytanie brzmi: czy istnieje sposób na bezpośrednie wygenerowanie tej listy, bez konieczności generowania wszystkich podzbiorów 2^n w pierwszej kolejności, ponieważ poprawi ona wydajność drastycznie, bez konieczności sprawdzania wszystkich elementów, ale raczej generowania ich "w locie" .

Answer 1

Jeśli chcesz zezwolić na całkowicie ogólne funkcje zamawiania, wówczas nie może być w stanie sprawdzać wszystkich elementów zestawu. (W końcu, jak byście wiedzieli, że nie jest to klauzula specjalna wbudowana, która daje, powiedzmy, konkretny zestaw [6,8,34,42] zupełnie innego rankingu od sąsiadów?)

Jednak można już drastycznie przyspieszyć algorytm przez

1. Tylko sortowania po filtrowania: sortowanie jest o (n & middot; log n), więc chcesz zachować n niski tutaj; w przypadku etapu filtrowania jest to mniej ważne. (W każdym razie liczba elementów nie zmienia się przez sortowanie.)
2. Zastosuj funkcję zamawiania tylko raz do każdego podzbioru.

Więc

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 

Zasadniczo, nie oszukujmy się, powersets z niczego, ale bardzo małe podstawy są nieosiągalne. Konkretna aplikacja “ sumująca się w pewnym zakresie ” jest prawie równa packaging problem; istnieją dość skuteczne sposoby na zrobienie tego rodzaju rzeczy, ale będziesz musiał zrezygnować z idealnej doskonałości i kwantyfikacji w stosunku do ogólnych podzbiorów.

Answer 2

Ponieważ Twój problem jest zasadniczo problemem z ograniczeniem ograniczeń, lepszym rozwiązaniem może być użycie zewnętrznego narzędzia do rozwiązywania problemów z SMT; zakładając, że możesz sobie pozwolić na dodatkowe IO w rodzaju i potrzebę zainstalowania takiego solwera. Biblioteka SBV pozwala na konstruowanie takich problemów.Oto jeden kodowania:

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] 

Dostajemy:

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

Dla dużych list, technika ta będzie pokonać generując wszystkie podgrupy i filtrowanie; zakładając, że funkcja kosztów generuje rozsądne ograniczenia. (Dodanie będzie zazwyczaj w porządku, jeśli masz multiplikacje, solver backend będzie miał trudniejszy czas.)

(Na marginesie, nie powinieneś nigdy używać filterM (const [True, False]) do generowania zestawów mocy na początek! Podczas gdy to wyrażenie jest urocza i zabawna, jest niesamowicie nieefektywna!)