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:
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
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:
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