Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: Iterating over combinations

by Limbic~Region (Chancellor)
on Sep 22, 2004 at 22:13 UTC ( #393064=note: print w/replies, xml ) Need Help??


in reply to Iterating over combinations

blokhead,
When I was working on this, I noticed revdiablo was generating all combinations of all sizes. I came up with a working solution to find only combinations of the desired size though it wasn't very elegant. I then sat down to figure out how I could make it generic for any size combinations (without having found this node) and came up with the following:
#!/usr/bin/perl use strict; use warnings; my $iter = combo( 5 , 1 .. 50 ); while ( my @combo = $iter->() ) { print "@combo\n"; } sub combo { my $by = shift; return sub { () } if ! $by || $by =~ /\D/ || @_ < $by; my @list = @_; my @position = (0 .. $by - 2, $by - 2); my @stop = @list - $by .. $#list; my $end_pos = $#position; my $done = undef; return sub { return () if $done; my $cur = $end_pos; { if ( ++$position[ $cur ] > $stop[ $cur ] ) { $position[ --$cur ]++; redo if $position[ $cur ] > $stop[ $cur ]; my $new_pos = $position[ $cur ]; @position[ $cur .. $end_pos ] = $new_pos .. $new_pos + + $by; } } $done = 1 if $position[0] == $stop[0]; return @list[ @position ]; } }
I didn't spend a lot of time benchmarking it. In some cases it does better than yours and then in others it does much worse. In any case, since I went through the trouble I figured I would add it here (now that I found it) in the spirit of TIMTOWTDI.

Cheers - L~R

Update: I kept the algorithm the same, but I made numerous optimizations. It is now much faster in the best case and only marginally slower than your method in the worst cases. The original is in HTML comments if anyone is interested.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://393064]
help
Chatterbox?
[Eily]: I'm leaving too, bye!
LanX leaves with a song of the Chjuman League
[ambrus]: LanX: that's funny because it's actually the upper class that sleep in hotels, so they're the ones who should know how it's pronounced

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (10)
As of 2017-03-27 17:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Should Pluto Get Its Planethood Back?



    Results (320 votes). Check out past polls.