Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re^4: Derangements iterator (callbacks)

by tye (Cardinal)
on Dec 29, 2005 at 19:56 UTC ( #519853=note: print w/ replies, xml ) Need Help??


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

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        


Comment on Re^4: Derangements iterator (callbacks)
Re^5: Derangements iterator (callbacks)
by Roy Johnson (Monsignor) on Dec 30, 2005 at 18:22 UTC
    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        

        Notwithstanding the fact that I bungled the code somewhere...what you call "my program" is effectively a translation of jdporter's program. Translated properly, it will return exactly the same results in exactly the same order. I've located my mistake and fixed.

        Caution: Contents may have been coded under pressure.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (13)
As of 2015-07-01 16:29 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 (11 votes), past polls