Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Better algorithm than brute-force stack for combinatorial problems? (A::L)

by tye (Sage)
on May 21, 2004 at 22:13 UTC ( [id://355482]=note: print w/replies, xml ) Need Help??


in reply to Better algorithm than brute-force stack for combinatorial problems?

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        

  • Comment on Re: Better algorithm than brute-force stack for combinatorial problems? (A::L)
  • Download Code

Replies are listed 'Best First'.
Re^2: Better algorithm than brute-force stack for combinatorial problems? (Benchmarks)
by tye (Sage) on May 21, 2004 at 22:42 UTC

    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
Re: Re: Better algorithm than brute-force stack for combinatorial problems? (Take 3 and homage to A::L)
by BrowserUk (Patriarch) on May 22, 2004 at 10:50 UTC

    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        

        Thanks. It'll probably take a few more readings to take that all in, but on the surface it makes (more) sense to me now. I think I was part way there with understanding the calling syntax and general methodology of the algorithm, but this clarifies it.

        The main problem I was commenting upon though is subtly different from understanding how to use NestedLoops. It's more a case of wrapping my brain around how to apply it to any given problem. I guess it is really no more complicated that coding a recursive routine and remembering that each piece of code will be run at all levels, but I've been doing recursion long enough that it has become second nature to think that way. This is like recursion, but different; and without the overhead.

        The subtly seems to be to the $sum[ @_ ] = ... bit. It took this post for me to realise that @sum isn't really an array in terms of the algorithm (the absence of the postfix 's' would be a clue if you normally hold to that convention). It's really a stack of autovivified, level-specific, persistant 'local' storage. (I think!).

        I stuck a print "@sum\n"; before the return in the OnlyWhen routine and it's interesting to watch the values iterate.

        This definitely requires a good "cookbook" article (or book?) to stimulate exploration of it's uses and algorithms. If you have the time TPJ were asking for authors:)


        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
      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...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://355482]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (4)
As of 2024-05-25 14:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found