Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: Recursively-generated Iterators

by Roy Johnson (Monsignor)
on Jun 02, 2005 at 01:53 UTC ( #462720=note: print w/ replies, xml ) Need Help??


in reply to Recursively-generated Iterators

Just another example of a conversion (using the boilerplate recipe). I'm posting mostly so it will be here to refer back to if I revisit the topic. It's interestingly different from the other examples, and the recipe still works well (although I get a curious Use of uninitialized value in array element warning if I don't turn those warnings off (which I do, below)).

What I'm generating is permutations, like Algorithm::Loops NextPermute.

#!perl use strict; use warnings; sub no_repeat_combos { return [@_] unless @_ > 1; # Find the first occurrence of each unique element my %seen; defined($seen{$_[$_]}) or $seen{$_[$_]} = $_ for 0..$#_; # For each unique element, stick it on the front of each # of the no-repeat-combos of the rest map { my $first_pos = $_; my @rest = @_[ grep {$first_pos != $_} 0..$#_ ]; map [$_[$first_pos], @$_], no_repeat_combos(@rest); } (sort {$a <=> $b} values %seen); } sub nrc_iter { # Base cases get assigned to an array, which the iterator shifts t +hrough my @base_case = ([@_]); return sub{ shift @base_case } unless @_ > 1; # Find the first occurrence of each unique element my %seen; defined($seen{$_[$_]}) or $seen{$_[$_]} = $_ for 0..$#_; # For each unique element, stick it on the front of each # of the no-repeat-combos of the rest my @arg_list = @_; my @sub_iter = map { my $first_pos = $_; my @rest = @_[ grep {$first_pos != $_} 0..$#_ ]; sub { my $recurse = nrc_iter(@rest); my $set; no warnings 'uninitialized'; sub { ($set = $recurse->()) ? [$arg_list[$first_pos], @$set] + : () } } } sort {$a <=> $b} values %seen; # Below here is boilerplate: if you've done the above steps right, + just plug # this in, and it works. It returns the first iterator from the li +st that # returns anything. # 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; } } for ([1], [1,1], [1,2], [qw(a b a)], [qw(a b b a)]) { print "=== @$_ ===\n"; my $i = nrc_iter(@$_); print " @$_\n" while $_ = $i->(); }

Caution: Contents may have been coded under pressure.


Comment on Re: Recursively-generated Iterators
Select or Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (5)
As of 2014-09-18 00:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (101 votes), past polls