Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re^3: Derangements iterator (callbacks)

by Roy Johnson (Monsignor)
on Dec 29, 2005 at 19:47 UTC ( #519846=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Derangements iterator (callbacks)
in thread Derangements iterator

It's not too difficult to go the other way using Recursively-generated Iterators.


Caution: Contents may have been coded under pressure.


Comment on Re^3: Derangements iterator (callbacks)
Re^4: Derangements iterator (callbacks)
by tye (Cardinal) on Dec 29, 2005 at 19:56 UTC

    I didn't have to rewrite my iterator, just use it. I believe you are pointing out ways to make it easier to rewrite a naive recursive solution so that it can be re-implemented as an iterator instead.

    By "Try to go the other way" I meant (at least in part), try to use jdporter's callback interface (as-is) in a situation where an iterator is needed.

    Though, I don't even understand what you linked to yet so I still consider what I did to go from iterator to callback to be "trivial" compared to what you are proposing as "not too difficult". (:

    - tye        

      I will agree that there's a distinct difference between "trivial" and "not too difficult" that applies to converting between iterators and recursive solutions. However, jd and I found it easier to write recursive solutions, so there's a trade-off in difficulty: It might be easier en toto to come up with a recursive one and then convert it to an iterator.

      Not even understanding jdporter's algorithm, I converted it to be iterative (or perhaps more precisely, lazily evaluated). I made the derange function print only the first 15 results, for convenient testing of large inputs.

      sub _derange_iter { my ($cb, $todo, @v) = @_; @$todo or return do { $cb->( @v ); sub {} }; # this line was wrong b +efore my %seen; @seen{@v} = (); my ( $range, @todo ) = @$todo; my @sub_iter = map { my $my_ = $_; sub { _derange_iter ( $cb, \@todo, @v, $my_ ) } } grep { ! exists $seen{$_} } @$range; return sub {} unless (@sub_iter); # Grab and unwrap an iterator from the list my $iter = (shift @sub_iter)->(); return sub { my $rval; $iter = (shift @sub_iter)->() until ($rval = $iter->() or @sub_iter == 0); return $rval; } } sub derange(&@) { my $cb = shift; my $iter = _derange_iter( $cb, [ map { my $x = $_; [ grep { $_ ne $x } @_ ] } @_ ] ); for (1..15) { $iter->(); } } derange { print "@_\n" } @ARGV;

      Caution: Contents may have been coded under pressure.

        But the iterator already existed. I find it easier to use the iterator to make a callback then to reimplement the algorithm recursively... (:

        But enough good-natured intentionally talking at cross purposes... I was curious in what order your program produced the derangements and it told me:

        b a d c b a d c b a d c b a d c ...

        So I'll still keep my iterator-from-the-get-go. ;)

        Update: If this "not too difficult" technique is too difficult for its own creator to correctly apply... And the point still stands that using an iterator via a call-back interface is trivial while using a call-back interface via an interator isn't even possible in stock Perl 5.

        - tye        

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (8)
As of 2015-07-06 09:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (70 votes), past polls