### Better algorithm than brute-force stack for combinatorial problems?

by Solo (Deacon)
 on May 21, 2004 at 20:22 UTC 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?

Replies are listed 'Best First'.
Re: Better algorithm than brute-force stack for combinatorial problems? (A::L)
by tye (Sage) 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

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

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

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? (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

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://355455]
Front-paged by Itatsumaki
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (5)
As of 2021-09-22 12:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?