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