Re: Algorithm::Loops::NestedLoops and LCS sequence (prune)


Clear questions and runnable code get the best and fastest answer
	PerlMonks

Re: Algorithm::Loops::NestedLoops and LCS sequence (prune)

by tye (Sage)

on Jun 14, 2004 at 07:11 UTC ( [id://366432]=note: print w/replies, xml )

Need Help??

in reply to Algorithm::Loops::NestedLoops and LCS sequence

Yes, the OnlyWhen routine does not "prune" deeper looping, it only controls whether your other code is called right then or not (which makes it seem rather useless when you look at it in some ways :).

As I was putting the module together, I tried a few different strategies for getting OnlyWhen to prune (by returning more than just true or false) and with an extra hook or two that could also be used to that purpose. I eventually backed off because it became clear that none of the schemes I had come up with were particularly great. So I hope to attack that challenge again and come up with a good scheme for adding more hooks to make it easy to prune (and to do other things).

In the mean time, you can use the technique, that I used in Re: Better algorithm than brute-force stack for combinatorial problems? (A::L), of having the loop specification code return [] if no deeper looping is desired.

- tye

Comment on Re: Algorithm::Loops::NestedLoops and LCS sequence (prune) Download Code

Replies are listed 'Best First'.

Re^2: Algorithm::Loops::NestedLoops and LCS sequence (prune)
by hv (Prior) on Jun 14, 2004 at 08:34 UTC

Ah, got it. I've modified the call to:

  NestedLoops(
    [ 
      ( sub {
        my $prefix = join '', @x[@_];
        [ grep !$seen{$prefix . $x[$_]}++, ($_ ? $_ + 1 : @_) .. $#x ]
+;
      } ) x $n,
    ],
    sub {
      my $ssx = join '', @x[@_];
      $count += (matchss($ssx, $y) or return) * matchss($ssx, $x);
    },
  );
[download]

%seen

Of course, now that I've unified the loop specifier, it feels slightly wasteful having to create $n copies of the same subref, but I can live with that. :)

Thanks for the help.

Hugo

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom