in reply to Re^8: Recursion problem
in thread Recursion problem

It was pointed out that I may have misunderstood your concerns with my first reply. That you were probably alluding to the fact that the code I offered the OP only detects the first possible matching sequence, rather than returning all possible sequences. I attempted to offer the OP a starting point from which to understand how to develop recursive solutions, rather than just hand him a complete solution on a plate.

That starting point can easily be extended to return the numbers involved in the (first) sequence detected:

sub sumTo { my $target = shift; for my $i ( 0 .. $#_ ) { return [ $_[ $i ] ] if $_[ $i ] == $target; if( @{ $_ = sumTo( $target - $_[ $i ], @_[ 0 .. $i-1, $i+1 .. $#_ + ] ) } ) { return [ $_[ $i ], @{ $_ } ]; } } return []; }

And that can be extended to produce all sequences as follows:

sub sumTo { my $target = shift; return map { $_[ $_ ] == $target ? [ $target ] : do{ my $x = $_[ $_ ]; map { @{ $_ } ? [ $x, @{ $_ } ] : () } sumTo( $target - $x, @_[ 0 .. $_-1, $_+1 .. $#_ ] ); }; } 0 .. $#_; } my @numbers = ( 5, -6, 8, 10, 12, 3, 10 ); print "$ARGV[ 0 ]: sum [@$_] => ", sum( @$_ ) for sumTo( $ARGV[ 0 ], @numbers ); __END__ [ 9:46:47.20] c:\test>688357 21 21: sum [5 -6 10 12] => 21 21: sum [5 -6 12 10] => 21 21: sum [5 -6 12 10] => 21 21: sum [5 -6 10 12] => 21 21: sum [5 10 -6 12] => 21 21: sum [5 10 12 -6] => 21 21: sum [5 12 -6 10] => 21 21: sum [5 12 -6 10] => 21 21: sum [5 12 10 -6] => 21 21: sum [5 12 10 -6] => 21 21: sum [5 10 -6 12] => 21 21: sum [5 10 12 -6] => 21 21: sum [-6 5 10 12] => 21 21: sum [-6 5 12 10] => 21 21: sum [-6 5 12 10] => 21 21: sum [-6 5 10 12] => 21 21: sum [-6 10 5 12] => 21 21: sum [-6 10 12 5] => 21 21: sum [-6 12 5 10] => 21 21: sum [-6 12 5 10] => 21 21: sum [-6 12 10 5] => 21 21: sum [-6 12 10 5] => 21 21: sum [-6 10 5 12] => 21 21: sum [-6 10 12 5] => 21 21: sum [8 10 3] => 21 21: sum [8 3 10] => 21 21: sum [8 3 10] => 21 21: sum [8 10 3] => 21 21: sum [10 5 -6 12] => 21 21: sum [10 5 12 -6] => 21 21: sum [10 -6 5 12] => 21 21: sum [10 -6 12 5] => 21 21: sum [10 8 3] => 21 21: sum [10 12 5 -6] => 21 21: sum [10 12 -6 5] => 21 21: sum [10 3 8] => 21 21: sum [12 5 -6 10] => 21 21: sum [12 5 -6 10] => 21 21: sum [12 5 10 -6] => 21 21: sum [12 5 10 -6] => 21 21: sum [12 -6 5 10] => 21 21: sum [12 -6 5 10] => 21 21: sum [12 -6 10 5] => 21 21: sum [12 -6 10 5] => 21 21: sum [12 10 5 -6] => 21 21: sum [12 10 -6 5] => 21 21: sum [12 10 5 -6] => 21 21: sum [12 10 -6 5] => 21 21: sum [3 8 10] => 21 21: sum [3 8 10] => 21 21: sum [3 10 8] => 21 21: sum [3 10 8] => 21 21: sum [10 5 -6 12] => 21 21: sum [10 5 12 -6] => 21 21: sum [10 -6 5 12] => 21 21: sum [10 -6 12 5] => 21 21: sum [10 8 3] => 21 21: sum [10 12 5 -6] => 21 21: sum [10 12 -6 5] => 21 21: sum [10 3 8] => 21

Each is a logical progression of the preceeding.


Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re^10: Recursion problem
by ysth (Canon) on May 26, 2008 at 17:31 UTC
    I was just exploring what felt like a quasi-contradiction in your argument. You seemed to be arguing that the solution of interest would be the first non-empty set, and I had trouble seeing where you'd want both the "non-empty" and the "first" qualifiers.