Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Permuting with duplicates and no memory

by dragonchild (Archbishop)
on Mar 12, 2002 at 22:05 UTC ( #151248=note: print w/replies, xml ) Need Help??


in reply to Permuting with duplicates and no memory

If you want a nice numeric permutation iterator-making closure (as I did), here's how I'd write it (based completely on the above node).
sub make_orderings { my $num = shift; my @arr = (1 .. $num); return sub { my $last = $#arr; my $i = $last - 1; $i-- while 0 <= $i && $arr[$i] >= $arr[$i+1]; return if $i == -1; @arr[$i+1..$last] = reverse @arr[$i+1..$last] if $arr[$i+1] > $arr[$last]; my $j=$i+1; $j++ while $arr[$i] >= $arr[$j]; @arr[$i,$j] = @arr[$j,$i]; return @arr; } }

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Replies are listed 'Best First'.
Re^2: Permuting with duplicates and no memory
by jettero (Monsignor) on Apr 01, 2007 at 15:01 UTC

    I borrowed this for something and noticed that if $num=8 this produces only 40319 permutations... I made the following el cheapo minor modification on mine.

    sub make_orderings { my $num = shift; my @arr = (1 .. $num); my $first = 1; return sub { if( $first ) { $first = 0; return @arr; } my $last = $#arr; my $i = $last - 1; $i-- while 0 <= $i && $arr[$i] >= $arr[$i+1]; return if $i == -1; @arr[$i+1..$last] = reverse @arr[$i+1..$last] if $arr[$i+1] > $arr[$last]; my $j=$i+1; $j++ while $arr[$i] >= $arr[$j]; @arr[$i,$j] = @arr[$j,$i]; return @arr; } }

    -Paul

      Just FYI, perhaps you missed this bit from the root node:

      do { print "@ARGV\n"; } while( nextPermut­e(@ARGV) );

      which is also why I called my routine "nextPermute".

      Also note that dragonchild's and my iterators can be reused. For yours to be reusable you probably want to change:

      return if $i == -1;

      to

      if( $i == -1 ) { $first= 1; return; }

      - tye        

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://151248]
help
Chatterbox?
[Corion]: ambrus: Yeah, at least that's what I think I'll start with. A timer and potentially the dummy IO function that never is ready
[ambrus]: That only lets you invoke the main loop from Prima->run;, not from AnyEvent->condvar- >recv; but that shouldn't matter
[Corion]: ambrus: Details ;)

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (8)
As of 2016-12-08 12:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    On a regular basis, I'm most likely to spy upon:













    Results (141 votes). Check out past polls.