Perl: the Markov chain saw 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)

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

Create A New User
Node Status?
node history
Node Type: note [id://519846]
help
Chatterbox?
 [shmem]: karlgoethebier: of course [shmem]: has there been any single day where nothing went wrong? not in my memory [shmem]: discovered a fuel tank leakage at my second hand motorbike. Some bloke drove a screw too long through the fairing [shmem]: hard to fix, and plans wrecked. And more... won't tell. [shmem]: the leakage has been "fixed" with a piece of bycicle tube. Bleargh. [karlgoethebier]: shmem: yes. my first ride tomorrow is questionable because of lumbago. shit

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (8)
As of 2017-06-25 19:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (570 votes). Check out past polls.