Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
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.


Comment on Re: Permuting with duplicates and no memory
Download Code
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?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (9)
As of 2015-07-06 11:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (73 votes), past polls