Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Better algorithm than brute-force stack for combinatorial problems?

by Solo (Deacon)
on May 21, 2004 at 20:22 UTC ( #355455=perlquestion: print w/ replies, xml ) Need Help??
Solo has asked for the wisdom of the Perl Monks concerning the following question:

I'm using a stack algorithm to solve a combinatorial problem--and I'm out of my comfort zone. This simplified example finds the subsets of a set of integers whos sum is a target number.

Searches on 'perl perl stack' or 'perl perl subset' proved rather off-topic, and 'combinatorial algorithm' was way out there. So I'm hoping for some constructive criticism here. For starters, is there a better/faster than brute-force algorithm? Or how about a more Perlish implementation? I feel like a C programmer ;p

Here's the code I'm using now.

use strict; my @block = qw/ 1 2 3 4 5 6 7 8 9 /; my $target = 20; my @solutions = solve($target,@block); print join(',',@$_) . "\n" for ( @solutions ); # find all combinations of blocks that sum to target sub solve { my ( $target, @block ) = @_; my ( @solutions, @trial, @stack ); my $acc = -1; NEW: while (1) { if ( sum( \@trial ) == $target ) { my @solu = @trial; push @solutions, \@solu; } OLD: while (1) { $acc++; if ( $acc <= $#block ) { push @trial, $block[$acc]; push @stack, $acc; next NEW; } elsif (@stack) { pop @trial; $acc = pop @stack; next OLD; } else { last NEW } } } return @solutions; } sub sum { local $_; my ($array) = @_; my $sum; $sum += $_ for (@$array); return $sum; }
TIA!

--Solo

Update: fixed a small code typo

--
You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.

Comment on Better algorithm than brute-force stack for combinatorial problems?
Download Code
Re: Better algorithm than brute-force stack for combinatorial problems?
by kvale (Monsignor) on May 21, 2004 at 21:12 UTC
    The problem you are solving is a variation of the Subset Sum problem, and is known to be NP complete. There exist algorithms that are a little better than brute force, but still exponential in the number of elements.

    Here is my take on the problem:

    my @check = qw/ 1 2 3 4 5 6 7 8 9 /; my $desired = 20; foreach my $index (0..2**@check-1) { my $sum = 0; foreach my $pos (0..@check-1) { my $bit = ($index >> $pos) % 2; $sum += $bit * $check[$pos]; } if ($sum == $desired) { my @combo; foreach my $pos (0..@check-1) { push @combo, $check[$pos] if ($index >> $pos) % 2; } print join " ", @combo, "\n"; } }
    On a 32 bit machine, this works for up to 32 numbers.

    -Mark

Re: Better algorithm than brute-force stack for combinatorial problems?
by BrowserUk (Pope) on May 21, 2004 at 22:12 UTC

    My take

    #! perl -slw use strict; use List::Util qw[ sum ]; sub Cnr{ my( $n, @r ) = shift; return [] unless $n--; for my $x ( 0 .. ($#_ - $n) ) { push @r, map{ [ $_[$x], @$_ ] } Cnr( $n, @_[ ($x + 1) .. $#_ ] ); } return @r; } sub sums{ my( $required, @values ) = @_; return grep{ sum( @$_ ) == $required ? $_ : () } map{ Cnr( $_, @values ) } 1 .. $#values; } print "@$_" for sums( 20, 1 .. 9 ); <STDIN>; __END__ P:\test>355455 3 8 9 4 7 9 5 6 9 5 7 8 1 2 8 9 1 3 7 9 1 4 6 9 1 4 7 8 1 5 6 8 2 3 6 9 2 3 7 8 2 4 5 9 2 4 6 8 2 5 6 7 3 4 5 8 3 4 6 7 1 2 3 5 9 1 2 3 6 8 1 2 4 5 8 1 2 4 6 7 1 3 4 5 7 2 3 4 5 6

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
Re: Better algorithm than brute-force stack for combinatorial problems? (A::L)
by tye (Cardinal) on May 21, 2004 at 22:13 UTC

    Here is a quick solution that is fairly efficient:

    #!/usr/bin/perl use strict; use warnings; use Algorithm::Loops qw( NestedLoops ); # Sum together subsets of these items: my @items= reverse 1..9; # The sum we wish to acheive: my $target= 20; # $sum[$N] == sum of first $N selected items: my @sum = 0; # Build an iterator that returns only lists of # indices for subsets that match our target sum: my $iter= NestedLoops( [ # First loop: all item indices [ 0..$#items ], # @items-1 subsequent loops: ( sub { # If we need more items: $sum[@_] < $target # then get more (unique) item indices ? [ ($_+1)..$#items ] # else don't get more items : [] } ) x $#items, ], { # Determine which subsets to return: OnlyWhen => sub { # Compute sum of selected items as # sum of @_-1 items plus last item: $sum[@_]= $sum[$#_] + $items[$_[-1]]; # Return subsets that match desired sum: return $sum[@_] == $target; }, }, ); # For each desired list of indices, get subset of items: while( my @list= @items[ $iter->() ] ) { warn "$target = sum( @list )\n"; }

    But my favorite part of this problem is that it is a perfect example to guide my plans for enhancing NestedLoops() to support custom actions each time the list is changed to make it extra easy to code these types of problems.

    - tye        

      Heh, changing the set to 1..20 and the desired sum to 30, I got the following run times:

      SecondsAuthor
      0tye
      10Solo
      24kvale
      673BrowserUK

      Just a quick, cheap benchmark. (:

      - tye        

        And that's the value of benchmarks :)


        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail

      My hat's of to you Sir! That is very, very cool code.

      At take 3, I managed to get your benchmark (30/1..20) down to under 1 second (675 ms) and with less than 10 MB with a new version and Memoize, but... for 40/1..20 I was up to 11s/98MB whereas your's did it in under half a second and 3 MB, even with the addition of accumulating the results in an AoA rather than printing them direct.

      My (pretty worthless) take 3 code

      The only problem I have (with the emphasis on I), is that even with the benefit of your commented code, I'm still not entirely sure that I understand how it works. I am certainly sure that I would not have been able to come up with the code (for this problem using Algorithm::Loops) myself.

      (FWIW) I've long been impressed by (your examples of using) A::L, I just can't wrap my brain around how to use it for non-trivial tasks like this.

      Off to re-read the documentation for the umpteenth time in the hope that something will click.


      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
        I agree BrowserUK. ++tye for an incredible module! I missed the original discussions of A::L last year, but went back and read most of them last night after completely failing to understand the source for NestedLoops()! The prior posts were no help, so this is how I grok'd his code eventually.

        I knew tye's approach was based on a closure as an iterator. Allright, I understand that, so I'll take what I understand and try to build it up to what NestedLoops() does...

        The first argument to NestedLoops is the list of loops so

        [ # First loop: all item indices [ 0..$#items ], # @items-1 subsequent loops: ( sub { # If we need more items: $sum[@_] < $target # then get more (unique) item indices ? [ ($_+1)..$#items ] # else don't get more items : [] } ) x $#items, ],

        becomes the equivalent of

        for $_ ( 0..$#items ) { # ... for $_ ( @{ $sum[@_] < $target ? [ ($_+1)..$#items ] : [] } ) { # ... for $_ ( @{ $sum[@_] < $target ? [ ($_+1)..$#items ] : [] } ) { # ... } } }

        The sub { ... } in the original code is required to delay the running of the loop computation code instead of running it before NestedLoops is called (at which point $_ and other variables wouldn't contain the rigth values).

        The list of items computed by the nested loops is passed to the subs as @_ and the currently innermost loop's variable is also put into $_ so you can use that as short-hand for $_[-1].

        And this bit

        OnlyWhen => sub { # Compute sum of selected items as # sum of @_-1 items plus last item: $sum[@_]= $sum[$#_] + $items[$_[-1]]; # Return subsets that match desired sum: return $sum[@_] == $target; },

        just declares a sub that gets called to determine which lists to return. We'll pretend it is named when() below. And we'll replace the @_ in each $sum[@_] with a hard-coded value to simplify our 'translation' which becomes something close to:

        @_= (); for $_ ( 0..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); for $_ ( @{ $sum[1] < $target ? [ ($_+1)..$#items ] : [] } ) { push @_, $_; push @return, [ @_ ] if when( @_ ); for $_ ( @{ $sum[2] < $target ? [ ($_+1)..$#items ] : [] } ) { push @_, $_; push @return, [ @_ ] if when( @_ ); # ... pop @_; } pop @_; } pop @_; }

        But instead of pushing each selected list into @return, each call to $iter->() returns the next list that would be pushed.

        Note that we loop over indices so we can use ($_+1)..$#items to only loop over indices that we haven't already looped over.

        Let's simplify the inner loops. The point of

        $sum[@_] < $target ? [ ($_+1)..$#items ] : []

        is to avoid looping any deeper if we don't need more items to add up (because we've already reached our desired total). Which can be more clearly written in our translation as

        next if $target <= $sum[@_];

        (if we do our pops in continue blocks) so we can clarify our example to

        @_= (); for $_ ( 0..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); next if $target <= $sum[1]; for $_ ( ($_+1)..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); next if $target <= $sum[2]; for $_ ( ($_+1)..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); # ... } continue { pop @_; } } continue { pop @_; } } continue { pop @_; }

        Of course, we can't finish this translation because you can't write loops that nest to some arbitrary depth.

        Fiinally, we use the iterator to get each desired set of indices. We use an array slice to convert the list of indices into a list of iitems:

        while( my @list= @items[ $iter->() ] ) { warn "$target = sum( @list )\n"; }

        I hope that helps explain how this works.

        - tye        

Re: Better algorithm than brute-force stack for combinatorial problems? (Take2)
by BrowserUk (Pope) on May 22, 2004 at 07:27 UTC

    With a fairly trivial change to my original (and plenty of ram!), it will handle tyes killer benchmark in a around 8 seconds.


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://355455]
Approved by sunadmn
Front-paged by Itatsumaki
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (7)
As of 2014-09-20 10:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (158 votes), past polls