Tạo trực tiếp các tập con cụ thể của một đại lý?

Question

biểu cảm của Haskell cho phép chúng tôi thay vì dễ dàng xác định một hàm Powerset:

import Control.Monad (filterM) 

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

Để có thể thực hiện nhiệm vụ của tôi nó là rất quan trọng cho biết Powerset được sắp xếp theo một chức năng cụ thể, vì vậy thực hiện của tôi loại trông như thế này :

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

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

Bây giờ câu hỏi của tôi là liệu có một cách để chỉ tạo ra một tập hợp con của Powerset cho một cụ thể start và end điểm, nơi f(start) < f(end) và |start| < |end|. Ví dụ, tham số của tôi là một danh sách các số nguyên ([1,2,3,4,5]) và chúng được sắp xếp theo tổng của chúng. Bây giờ tôi chỉ muốn trích xuất các tập hợp con trong một phạm vi nhất định, giả sử 3 đến 7. Một cách để đạt được điều này sẽ được filter các Powerset để chỉ bao gồm phạm vi của tôi, nhưng điều này dường như (và là) không hiệu quả khi đối phó với các tập con lớn hơn:

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] sản xuất [[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]].

Bây giờ câu hỏi của tôi là có cách tạo danh sách này trực tiếp, mà không phải tạo tất cả các tập hợp con 2^n trước vì nó sẽ cải thiện hiệu suất mạnh mẽ bằng cách không phải kiểm tra tất cả các yếu tố mà là tạo chúng "nhanh" .

Answer 1

Nếu bạn muốn cho phép các chức năng đặt hàng hoàn toàn chung, thì không thể là cách kiểm tra tất cả các thành phần của thiết bị. (Sau khi tất cả, làm thế nào bạn sẽ biết không phải là một điều khoản đặc biệt được xây dựng trong đó cung cấp cho, nói rằng, các thiết lập cụ thể [6,8,34,42] một thứ hạng hoàn toàn khác nhau từ các nước láng giềng?)

Tuy nhiên, bạn có thể làm cho thuật toán đã nhanh hơn đáng kể bởi

1. Chỉ sắp xếp sau lọc: phân loại là O (n & chấm giữa; log n), do đó bạn muốn giữ n thấp ở đây; cho các bước O (n), việc lọc bước quan trọng hơn. (Và dù sao, số lượng các yếu tố không thay đổi thông qua phân loại.)
2. Chỉ áp dụng chức năng đặt hàng một lần cho mỗi tập hợp con.

Vì vậy

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 

Về cơ bản, chúng ta hãy đối mặt với nó, powersets bất cứ điều gì nhưng một cơ sở rất nhỏ là không khả thi. Các ứng dụng cụ thể “ tổng trong một phạm vi nhất định ” là khá nhiều một packaging problem; có những cách khá hiệu quả để làm điều đó, nhưng bạn sẽ phải từ bỏ ý tưởng về tính tổng quát hoàn hảo và định lượng trên các tập con chung.

Answer 2

Vì vấn đề của bạn về cơ bản là một vấn đề về độ hạn chế, việc sử dụng bộ giải quyết SMT bên ngoài có thể là giải pháp thay thế tốt hơn ở đây; giả sử bạn có thể đủ khả năng IO thêm trong loại và sự cần thiết cho một người giải quyết như vậy sẽ được cài đặt. Thư viện NHNN cho phép xây dựng các vấn đề như vậy.Dưới đây là một mã hóa:

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] 

Chúng tôi nhận được:

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

Đối với các danh sách lớn, kỹ thuật này sẽ đánh bại tạo ra tất cả các tập con và lọc; giả sử hàm chi phí tạo ra các ràng buộc hợp lý. (Bổ sung sẽ thường là OK, nếu bạn đã nhân, bộ giải trợ phụ trợ sẽ có thời gian khó hơn.)

(Lưu ý rằng bạn không nên sử dụng filterM (const [True, False]) để tạo bộ nguồn để bắt đầu! dễ thương và vui vẻ, cực kỳ không hiệu quả!)