On 4/22/2012 11:18 PM, Chris Rebert wrote:
On Sun, Apr 22, 2012 at 7:55 PM, Terry Reedy<tjreedy@udel.edu> wrote:
On 4/22/2012 9:07 PM, Nestor wrote: <snip>
false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should print true because 4 + 6 + 10 + 3 = 23.
Since the order of the numbers is arbitrary and irrelevant to the problem, it should be formulated in term of a set of numbers.
Er, multiplicity still matters, so it should be a multiset/bag. One possible representation thereof would be a list...
Er, yes. Given the examples, I (too quickly) misread 'will not contain all the same elements' as 'no duplicates'. In any case, a set was needed
And doesn't ordering matter too (for efficiency). A sorted list of the positive integers may solve in much less less time, right?
On 4/24/2012 7:10 PM, Hobson Lane wrote:
And doesn't ordering matter too (for efficiency). A sorted list of the positive integers may solve in much less less time, right?
The OP gave the brute-force solution of testing all subsets as a justification for adding a powerset iterator. With negative numbers allowed (as in this problem), that may be the best one can do. But if negatives are excluded, sorting allows a pruning strategy. For instance, all subsets can be separated in to those with and without the 2nd highest. For those with the 2nd highest, one only need consider the initial slice of numbers <= hi - 2nd_hi. If two numbers add to more than the target, then all larger subsets containing the pair can be excluded and not generated and summed. One can apply this idea recursively. But there is no guarantee of any saving. -- Terry Jan Reedy
On 4/24/2012 8:09 PM, Terry Reedy wrote:
On 4/24/2012 7:10 PM, Hobson Lane wrote:
And doesn't ordering matter too (for efficiency). A sorted list of the positive integers may solve in much less less time, right?
The OP gave the brute-force solution of testing all subsets as a justification for adding a powerset iterator. With negative numbers allowed (as in this problem), that may be the best one can do.
But if negatives are excluded, sorting allows a pruning strategy. For instance, all subsets can be separated in to those with and without the 2nd highest. For those with the 2nd highest, one only need consider the initial slice of numbers <= hi - 2nd_hi. If two numbers add to more than the target, then all larger subsets containing the pair can be excluded and not generated and summed. One can apply this idea recursively. But there is no guarantee of any saving.
As an algorithm question and answer, this is off topic. However, it reinforces Nick's claim that powerset() is not too useful because "In practice, you'll be doing prefiltering and other conditioning on your combinations to weed out nonsensical variants cheaply," -- Terry Jan Reedy
participants (2)
-
Hobson Lane -
Terry Reedy