Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

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)

Replies are listed 'Best First'.
Re^4: Derangements iterator (callbacks)
by tye (Sage) 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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://519846]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (5)
As of 2018-01-18 08:29 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (208 votes). Check out past polls.