Permutations/Rank of a permutation: Difference between revisions

=={{header|Perl}}==

The ntheory module gives us <code>numtoperm</code> and <code>permtonum</code> commands similar to Pari/GP, though in the preferred lexicographic order. Values larger than the native int size are handled as well. The <code>randperm</code> function is useful for random permutations, using a Knuth shuffle and a Chacha/20 CSPRNG supplying randomness. A Macbook takes a bit under 4 seconds to generate 1 million random permutations of 144 objects, or 8 seconds if inserting into a set to ensure uniqueness.

{{libheader|ntheory}}

<lang perl>use ntheory qw/:all/;

my $n = 3;

print " Iterate Lexicographic rank/unrank of $n objects\n";

for my $k (0 .. factorial($n)-1) {

my @perm = numtoperm($n, $k);

my $rank = permtonum(\@perm);

die unless $rank == $k;

printf "%2d --> [@perm] --> %2d\n", $k, $rank;

}

print "\n";

print " Four 12-object random permutations using ranks\n";

print join(" ", numtoperm(12,urandomm(factorial(12)))), "\n" for 1..4;

print "\n";

print " Four 12-object random permutations using randperm\n";

print join(" ", randperm(12)),"\n" for 1..4;

print "\n";

print " Four 4-object random permutations of 100k objects using randperm\n";

print join(" ", randperm(100000,4)),"\n" for 1..4;

</lang>

{{out}}

<pre>

Iterate Lexicographic rank/unrank of 3 objects

0 --> [0 1 2] --> 0

1 --> [0 2 1] --> 1

2 --> [1 0 2] --> 2

3 --> [1 2 0] --> 3

4 --> [2 0 1] --> 4

5 --> [2 1 0] --> 5

Four 12-object random permutations using ranks

0 6 1 4 2 5 3 7 8 9 11 10

4 2 8 6 0 3 9 10 7 11 5 1

6 1 7 2 4 5 3 0 11 10 8 9

0 2 3 9 10 1 4 7 11 8 6 5

Four 12-object random permutations using randperm

1 7 5 6 2 9 0 3 10 11 4 8

6 11 7 2 5 4 0 9 3 8 1 10

1 9 6 11 10 8 4 0 2 3 5 7

10 0 1 8 7 4 5 6 11 3 9 2

Four 4-object random permutations of 100k objects using randperm

51080 2774 79078 28078

38822 21928 77796 36832

6089 14383 3397 31577

61539 80497 47550 53322

</pre>