Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

Re: Recursively-generated Iterators

by runrig (Abbot)
on May 20, 2005 at 04:39 UTC ( #458851=note: print w/replies, xml ) Need Help??

in reply to Recursively-generated Iterators

I had my own idea of how to do it, and I came up with restartable iterators:
#!/usr/bin/perl use strict; use warnings; sub restartable_iter { my ($start, $end) = @_; sub { $start = shift if @_; return if $start > $end; $start++; } } sub choose_m_of_n_iter { my ($m, $n) = @_; my @iter; for my $i (0..($m-1)) { push @iter, restartable_iter($i, $n-$m+$i); } join_iter(@iter); } sub join_iter { my $it = shift; while ( my $tmp = shift ) { $it = append_iter( $it, $tmp ); } $it; } sub append_iter { my ($it1, $it2) = @_; my (@ret1, @ret2) = $it1->(); sub { return @ret1, @ret2 if @ret2 = $it2->(); return unless @ret1 = $it1->(); return @ret1, $it2->($ret1[-1]+1); } } my $iter = choose_m_of_n_iter(4, 10); while (my @arr = $iter->()) { print "@arr\n"; }

In the append iterator, when the second iterator is exhausted, it causes the first iterator to iterate, and then restarts the second iterator at the appropriate starting point.

Update:Unlike the other solutions, the solution above returns an array of indices instead of a set of elements from a list, but that's easy to adjust:

sub choose_n { my $n = shift; my @set = @_; my $iter = choose_m_of_n_iter($n, scalar(@set)); sub { @set[$iter->()]; } }

Update: Simplified code. Which may or may not be a good thing :-)

Replies are listed 'Best First'.
Re^2: Recursively-generated Iterators
by Roy Johnson (Monsignor) on May 23, 2005 at 17:11 UTC
    I was not able to figure out what your strategy is. Could you describe what a restartable iterator is, and what problem it addresses?

    Caution: Contents may have been coded under pressure.
      Could you describe what a restartable iterator is, and what problem it addresses?

      Well, I made up the name (and so maybe it's a badly chosen name), but what I mean is, an iterator whose behaviour you can modify after it has already started (in this case, it's a simple iterator, but I can restart it at any point each time it is exhausted). In iterating over the result set, I noticed that in choosing M out of a set of N objects (in a normal nested for loop way), the inner most loop would iterate from M to N, then from M+1 to N, then M+2 to N, etc (down to N to N), while the next outer loop would iterate from M-1 to N-1, then from M to N-1, then M+1 to N-1, etc. The outer most loop just iterates from 1 to N-M+1 (assuming the array index starts at 1, though in above program it starts at zero).

      That was the basic pattern at first, but it was more complicated eventually, because the first time that the innermost iterator got down to the "N to N" iteration, it would have to restart at M+1 at the next iteration. So I thought it might be easier to construct an iterator that could tell the next "inner" iterator where to start (the ending point is always the same for each iterator in this case). The iterators I've seen so far return a function that accepts no arguments, but in my "restartable_iter()", it returns a function that can accept a new starting point.

      This, of course, is not a generic solution for all iteration problems, because one iterator must be aware of how to tell the next iterator in line what to do. But it was fun to come up with.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (3)
As of 2022-12-02 10:04 GMT
Find Nodes?
    Voting Booth?