Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re^5: Derangements iterator (callbacks)

by Roy Johnson (Monsignor)
on Dec 30, 2005 at 18:22 UTC ( #520038=note: print w/ replies, xml ) Need Help??


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

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.


Comment on Re^5: Derangements iterator (callbacks)
Download Code
Replies are listed 'Best First'.
Re^6: Derangements iterator (callbacks)
by tye (Cardinal) on Dec 30, 2005 at 19:11 UTC

    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://520038]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (15)
As of 2015-07-07 17:34 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 (93 votes), past polls