filter-maximal.rkt (2040B)
1 #lang racket/base 2 3 (provide filter-maximal) 4 5 (module+ test 6 (require rackunit 7 (only-in racket/list in-permutations) 8 (only-in racket/set set=? subset?))) 9 10 ;; filter-maximal : [Listof X] [X X -> Bool] -> [Listof X] 11 ;; <? is a partial ordering predicate 12 (define (filter-maximal xs <?) 13 (reverse 14 (for/fold ([acc '()]) 15 ([x (in-list xs)]) 16 (merge-with x acc <?)))) 17 18 ;; merge-with : X [Listof X] [X X -> Bool] -> [Listof X] 19 ;; <? is a partial ordering predicate 20 (define (merge-with x ys <?) 21 (define (greater? y) (<? x y)) 22 (cond [(ormap greater? ys) ys] 23 [else 24 (define (not-lesser? y) (not (<? y x))) 25 (cons x (filter not-lesser? ys))])) 26 27 ;; ---------------------------------------------------------------------------- 28 29 (module+ test 30 (define-check (check-filter-maximal lst <? expected) 31 (test-begin 32 (for ([p (in-permutations lst)]) 33 (check set=? (filter-maximal p <?) expected)))) 34 35 (check-equal? (filter-maximal '(1 2 3 2 3 2 1) <) '(3 3)) 36 (check-equal? (filter-maximal '(1 2 3 2 3.0 2 1) <) '(3 3.0)) 37 (check-equal? (filter-maximal '(1 2 3.0 2 3 2 1) <) '(3.0 3)) 38 39 (check-equal? (filter-maximal '({} {a} {b} {c}) subset?) '({a} {b} {c})) 40 (check-equal? (filter-maximal '({b} {} {a} {c}) subset?) '({b} {a} {c})) 41 (check-equal? (filter-maximal '({c} {b} {a} {}) subset?) '({c} {b} {a})) 42 43 (check-filter-maximal '({} {a} {b}) subset? '({a} {b})) 44 (check-filter-maximal '({} {a} {b} {a b}) subset? '({a b})) 45 (check-filter-maximal '({} {a} {b} {c} {a b}) subset? '({a b} {c})) 46 (check-filter-maximal '({} {a} {b} {c} {a b} {c a} {b c}) subset? 47 '({a b} {c a} {b c})) 48 (check-filter-maximal '({} {a} {b} {c} {a b} {c a} {b c}) subset? 49 '({a b} {c a} {b c})) 50 (check-filter-maximal '({} {a} {b} {c} {b c d} {a b} {c a} {b c}) subset? 51 '({a b} {c a} {b c d})) 52 (check-filter-maximal '({} {a} {b} {c} {a b c d} {a b} {c a} {b c}) subset? 53 '({a b c d})) 54 )