Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
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; }


Update: fixed a small code typo

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

In reply to Better algorithm than brute-force stack for combinatorial problems? by Solo

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chilling in the Monastery: (1)
As of 2024-05-25 14:35 GMT
Find Nodes?
    Voting Booth?

    No recent polls found