First solution:
(defn groupSum [l x]
(or (zero? x) ; we have won!
(and (not ( x 0)) ; we can't win
(not (empty? l)) ; lost!
(or (groupSum (rest l) (- x (first l)))
(recur (rest l) x)
The we
This is the classic Subset sum problem
(http://en.wikipedia.org/wiki/Subset_sum_problem) and is an NP one.
I've implemented the pseudo-polynomial dynamic programming solution found
on the above Wikipedia page:
https://gist.github.com/3359504
It returns the indexes of the elements that give the
¿
take the first #.
subtract that from the goal.
now ask if the remaining #s can sum to the now-lesser goal.
lather rinse repeat.
don't forget a base case.
watch your cpu heat very quickly up on even slightly longer lists.
?
On Tue, Aug 14, 2012 at 4:13 PM, John Holland jbholl...@gmail.com wrote:
sorry take the first# actually is meant to be worded as, in turn,
take out 1 of each of the #s, and recurse on what remains so that you
are doing the permutations at each level of the recursion/tree.
On Tue, Aug 14, 2012 at 4:15 PM, Raoul Duke rao...@gmail.com wrote:
¿
take the first #.
I thought of doing something like that, but part of the requirements is
that the sum could be achieved with *some of the numbers in the vector.
On Tuesday, August 14, 2012 7:15:27 PM UTC-4, raould wrote:
¿
take the first #.
subtract that from the goal.
now ask if the remaining #s can sum
On Tue, Aug 14, 2012 at 4:17 PM, John Holland jbholl...@gmail.com wrote:
I thought of doing something like that, but part of the requirements is that
the sum could be achieved with *some of the numbers in the vector.
in the stupidest approach that is just the same thing as all of the
numbers in
On Tue, Aug 14, 2012 at 4:17 PM, John Holland jbholl...@gmail.com wrote:
I thought of doing something like that, but part of the requirements is that
the sum could be achieved with *some of the numbers in the vector.
the other way of looking at it is that the recursion just quits once
the sum
An additional step on top of Raoul's:
Take the first #, subtract it from the goal, recursively ask if the remaining
#s can sum to the now-lesser goal. If so, return yes, or the set of numbers
that worked (which should include whatever was returned from the recursive
call, plus the first #)
Thanks for all the help!
On Tuesday, August 14, 2012 7:38:58 PM UTC-4, Andy Fingerhut wrote:
An additional step on top of Raoul's:
Take the first #, subtract it from the goal, recursively ask if the
remaining #s can sum to the now-lesser goal. If so, return yes, or the set
of numbers
Ended up with the following wondering if loop/recur is possible in this
case?
(defn groupSum [a x] (cond
(= (count a) 0) false
(= (first a) x) true
( (first a) x) (if ( (count a) 1) (groupSum (rest
a) x) false)
10 matches
Mail list logo
