*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.

Back to
Seekers of Perl Wisdom

Comment onBetter algorithm than brute-force stack for combinatorial problems?DownloadCode