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

In such a case, you'd want all possible subsets of debits and credits that sum to zero, wouldn't you?

Replies are listed 'Best First'.
Re^9: Recursion problem
by BrowserUk (Patriarch) on May 26, 2008 at 08:57 UTC

    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.
      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.
Re^9: Recursion problem
by BrowserUk (Patriarch) on May 25, 2008 at 21:31 UTC

    All, except the empty set case. Eventually you might need to investigate further to see if one such set was consistant with other information--order and delivery notes etc.--but initially, just whether any such (non-empty) set existed might be a useful boolean. But it would be rendered meaningless if the empty set is considered a match.

    In truth, it was just the first example I thought of that supported my argument. However, hard as I might try, I cannot think of a counter example. Not one.


    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.