; floupia
(define (filter pred? xs)
(let loop ((xs xs) (ys '()))
(cond ((null? xs) (reverse ys))
((pred? (car xs))
(loop (cdr xs) (cons (car xs) ys)))
(else (loop (cdr xs) ys)))))
(define (sum xs) (apply + xs))
(define (negate x) (- x))
(define (binom n m)
(let loop ((n n) (m m) (b 1))
(if (zero? m) b
(loop (- n 1) (- m 1) (* b n (/ m))))))
(define (combinations-without-replacement n xs)
(if (= n 0) (list (list))
(if (null? xs) (list)
(append (map (lambda (xss) (cons (car xs) xss))
(combinations-without-replacement (- n 1) (cdr xs)))
(combinations-without-replacement n (cdr xs))))))
(display (binom 5 3)) (newline)
(display (combinations-without-replacement 3 '(a b c d e))) (newline)
(define (combinations-with-replacement n xs)
(if (= n 0) (list (list))
(if (null? xs) (list)
(append (map (lambda (xss) (cons (car xs) xss))
(combinations-with-replacement (- n 1) xs))
(combinations-with-replacement n (cdr xs))))))
(display (binom (+ 5 3 -1) 3)) (newline)
(display (combinations-with-replacement 3 '(a b c d e))) (newline)
(define (floupia price coins)
(if (positive? (modulo price (apply gcd coins)))
(error 'floupia "infeasible")
(let ((coins (append coins (map negate coins))))
(let loop ((n 1))
(let ((xs (filter (lambda (xs) (= (sum xs) price))
(combinations-with-replacement n coins))))
(if (null? xs) (loop (+ n 1)) xs))))))
(display (floupia 13 '(2 5 10))) (newline)
(display (floupia 18 '(1 2 5 10))) (newline)
(display (floupia 17 '(1 3 7 31 153))) (newline)
(display (floupia 11 '(3 6))) (newline)