Perl Monk, Perl Meditation 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??

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.

Create A New User
Node Status?
node history
Node Type: note [id://462720]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2018-05-25 21:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (191 votes). Check out past polls.

Notices?