perlquestion
Solo
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.<p>
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<p>
Here's the code I'm using now.
<readmore>
<code>
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;
}
</code>
<div class="pmsig">
<div class="pmsig-195975">
TIA!<p>
--Solo<p>
<b>Update:</b> fixed a small code typo<p>
<font size=1><i><blockquote>--<br>
You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.
</blockquote></i></font>
</div></div>