note
tye
<p>
The first argument to NestedLoops is the list of loops so
</p><code>
[
# 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,
],
</code><p>
becomes the equivalent of
</p><code>
for $_ ( 0..$#items ) {
# ...
for $_ ( @{ $sum[@_] < $target
? [ ($_+1)..$#items ] : [] }
) {
# ...
for $_ ( @{ $sum[@_] < $target
? [ ($_+1)..$#items ] : [] }
) {
# ...
}
}
}
</code><p>
The <tt>sub { ... }</tt> 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).
</p><p>
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 <code>$_[-1]</code>.
</p><p>
And this bit
</p><code>
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;
},
</code><p>
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 <code>$sum[@_]</code> with a hard-coded value to simplify our 'translation' which becomes something close to:
</p><code>
@_= ();
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 @_;
}
</code><p>
But instead of pushing each selected list into @return, each call to <code>$iter->()</code> returns the next list that would be pushed.
</p><p>
Note that we loop over indices so we can use <code>($_+1)..$#items</code> to only loop over indices that we haven't already looped over.
</p><p>
Let's simplify the inner loops. The point of
</p><code>
$sum[@_] < $target ? [ ($_+1)..$#items ] : []
</code><p>
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
</p><code>
next if $target <= $sum[@_];
</code><p>
(if we do our [pop]s in [continue] blocks) so we can clarify our example to
</p><code>
@_= ();
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 @_;
}
</code><p>
Of course, we can't finish this translation because you can't write loops that nest to some arbitrary depth.
</p><p>
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:
</p><code>
while( my @list= @items[ $iter->() ] ) {
warn "$target = sum( @list )\n";
}
</code><p>
I hope that helps explain how this works.
</p>
<div class="pmsig"><div class="pmsig-22609"><p align="right">
- [tye]<tt> </tt>
</p></div></div>
355455
355571