Anonymous user
Subset sum problem: Difference between revisions
Added EchoLisp
m (J: mention why we are not showing all solutions here) |
(Added EchoLisp) |
||
Line 365:
{{out}}
<pre>Zero sums: 349167</pre>
=={{header|EchoLisp}}==
We use the Pseudo-polynomial time dynamic programming solution, found in the [[wp:Subset sum problem|Subset sum problem]] Wikipedia article. If A and B are the min and max possible sums, the time and memory needed are '''O((B-A)*N)'''. '''Q''' is an array such as Q(i,s) = true if there is a nonempty subset of x0, ..., xi which sums to s.
<lang scheme>
;; 0 <= i < N , A <= s < B , -A = abs(A)
;; mapping two dims Q(i,s) to one-dim Q(qidx(i,s)) :
(define-syntax-rule (qidx i s) (+ i (* (+ s -A) N)))
;; filling the Q array with true/false values
;; Q(i, s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi), for A ≤ s < B.
(define (fillQ xs (ds))
(define N (length xs))
(define A (apply + (filter negative? xs)))
(define B (1+ (apply + (filter positive? xs))))
(define -A (abs A))
(define Q (make-vector (* N (- B A))))
(set! xs (list->vector xs))
(printf "Q[%d] allocated." (vector-length Q))
(for ((s (in-range A B)))
(vector-set! Q (qidx 0 s ) (= [xs 0] s)))
(for* ([i (in-range 1 N)]
[s (in-range A B)])
(set! ds (- s [xs i]))
(vector-set! Q (qidx i s)
(or
[Q (qidx (1- i) s)]
(= [xs i] s)
(and (>= ds A) (< ds B) [Q (qidx (1- i) ds )])))
;; stop on first zero-sum found
#:break (and (zero? s) [Q (qidx i s)]) => (solQ Q xs i s -A N)
))
;; backtracking to get the list of i's such as sum([xs i]) = 0
;; start from q[i,0] === true
(define (solQ Q xs i s -A N (sol null))
(cond
(( = s [xs i]) (cons i sol))
([Q (qidx (1- i ) s)] (solQ Q xs (1- i) s -A N sol))
(else (solQ Q xs (1- i) (- s [xs i]) -A N (cons i sol)))))
(define (task input)
(map (lambda(i) (first (list-ref input i))) (fillQ (map rest input))))
</lang>
{{out}}
<pre>
(define input
'({"alliance" . -624}
{"archbishop" . -915}
{"balm" . 397}
{"bonnet" . 452}
{"brute" . 870}
{"centipede" . -658}
{"cobol" . 362}
{"covariate" . 590}
{"departure" . 952}
{"deploy" . 44}
{"diophantine" . 645}
{"efferent" . 54}
{"elysee" . -326}
{"eradicate" . 376}
{"escritoire" . 856}
{"exorcism" . -983}
{"fiat" . 170}
{"filmy" . -874}
{"flatworm" . 503}
{"gestapo" . 915}
{"infra" . -847}
{"isis" . -982}
{"lindholm" . 999}
{"markham" . 475}
{"mincemeat" . -880}
{"moresby" . 756}
{"mycenae" . 183}
{"plugging" . -266}
{"smokescreen" . 423}
{"speakeasy" . -745}
{"vein" . 813}))
(task input)
Q[587016] allocated.
→ ("archbishop" "balm" "bonnet" "centipede" "cobol" "covariate"
"deploy" "efferent" "elysee")
;; using Haskell test data
(define items
'[-61 1 32 373 311 249 311 32 -92 -185 -433
-402 -247 156 125 249 32 -464 -278 218 32 -123
-216 373 -185 -402 156 -402 -61 -31 902 ])
(map (lambda(i) (list-ref items i)) (fillQ items))
Q[221185] allocated.
→ (-61 32 373 311 249 311 32 -92 -185 -433 -402 -247 156 125 249 32 -
464 -278 218 32 -123 -216 373 -185 -402 156 -402 -61 902)
</pre>
=={{header|FunL}}==
| |||