Re: recursion question
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 can't win line assume that all numbers are positive. We use tail recursion in the only place we can use it. If all numbers are positive, a more elaborate version would use this fact: If all numbers are positive, and the sum of a suffix can't reach a target, you should not try without the first element. So the function will return : - either 0 if we reach the goal - a negative number if we went over the goal - a positive number if we went under the goal. If we went under the goal, we don't need to try without the first element. (defn groupSum0 [l n] (if (or (empty? l) ( n 0)) n (let [res (groupSum0 (rest l) (- n (first l)))] (if (= res 0) res ;; we are either winning or can't reach the goal (if (zero? (groupSum0 (rest l) n)) 0 ;; we have won res) ;; we repeat we can reach the goal from here (defn groupSum [l n] (zero? (groupSum0 l n))) Next step would be to make groupSum0 not stack overflow on big inputs and to add memoization to it. Best regards, Nicolas. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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 desired sum but it can trivially be transformed to whether there is a solution or not. Balint On Wednesday, August 15, 2012 1:13:32 AM UTC+2, John Holland wrote: I've been doing some programming exercises in Clojure, I've run into one I don't know how to approach. If anyone can just give me the strategy to use on this that'd be great. Here is the problem statement: Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? sample calls would be like: (groupSum [2, 4, 8] 10) → true (groupSum [2, 4, 8] 14) → true (groupSum [2, 4, 8] 9) → false -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
¿ 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: I've been doing some programming exercises in Clojure, I've run into one I don't know how to approach. If anyone can just give me the strategy to use on this that'd be great. Here is the problem statement: Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? sample calls would be like: (groupSum [2, 4, 8] 10) → true (groupSum [2, 4, 8] 14) → true (groupSum [2, 4, 8] 9) → false -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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 #. 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: I've been doing some programming exercises in Clojure, I've run into one I don't know how to approach. If anyone can just give me the strategy to use on this that'd be great. Here is the problem statement: Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? sample calls would be like: (groupSum [2, 4, 8] 10) → true (groupSum [2, 4, 8] 14) → true (groupSum [2, 4, 8] 9) → false -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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 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 jbho...@gmail.comjavascript: wrote: I've been doing some programming exercises in Clojure, I've run into one I don't know how to approach. If anyone can just give me the strategy to use on this that'd be great. Here is the problem statement: Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? sample calls would be like: (groupSum [2, 4, 8] 10) → true (groupSum [2, 4, 8] 14) → true (groupSum [2, 4, 8] 9) → false -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@googlegroups.comjavascript: Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+u...@googlegroups.com javascript: For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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 the vector with a generator/filter up front that spits out all the possible 1 length vectors, 2 length vectors, etc. derived from the total vector? boy i'm just making you think along worse lines performance-wise, aren't i? like the republicans say, just do the opposite of whatever i'm saying to do... :-) -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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 it is carrying along is the desired sum. instead of always reaching the base case of a unit-length-vector. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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 #) If not, recursively ask if the remaining #s can sum to the original goal. If so return yes, or the set of numbers that worked (which does not include the first #) In the worst case, that will try all 2^n possible subsets of the collection of numbers, and then return false. There are dynamic programming methods that work faster if the sum of the numbers is small enough, but require holding in memory an array of at least N bits, where N is the target. Andy On Aug 14, 2012, at 4:17 PM, John Holland 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. 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 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 jbho...@gmail.com wrote: I've been doing some programming exercises in Clojure, I've run into one I don't know how to approach. If anyone can just give me the strategy to use on this that'd be great. Here is the problem statement: Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? sample calls would be like: (groupSum [2, 4, 8] 10) → true (groupSum [2, 4, 8] 14) → true (groupSum [2, 4, 8] 9) → false -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+u...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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 that worked (which should include whatever was returned from the recursive call, plus the first #) If not, recursively ask if the remaining #s can sum to the original goal. If so return yes, or the set of numbers that worked (which does not include the first #) In the worst case, that will try all 2^n possible subsets of the collection of numbers, and then return false. There are dynamic programming methods that work faster if the sum of the numbers is small enough, but require holding in memory an array of at least N bits, where N is the target. Andy On Aug 14, 2012, at 4:17 PM, John Holland 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. 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 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 jbho...@gmail.com wrote: I've been doing some programming exercises in Clojure, I've run into one I don't know how to approach. If anyone can just give me the strategy to use on this that'd be great. Here is the problem statement: Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target? sample calls would be like: (groupSum [2, 4, 8] 10) → true (groupSum [2, 4, 8] 14) → true (groupSum [2, 4, 8] 9) → false -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+u...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clo...@googlegroups.com javascript: Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+u...@googlegroups.com javascript: For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: recursion question
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) :else (or (groupSum (rest a) (- x (first a))) (groupSum (rest a) x -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
