Permutations/Rank of a permutation: Difference between revisions
Content deleted Content added
Added Kotlin |
Add Perl |
||
Line 1,082:
<pre>%1 = 1
%2 = [[3, 11, 7, 9, 10, 5, 2, 12, 8, 1, 4, 6], [11, 9, 6, 1, 5, 3, 10, 2, 7, 4, 12, 8], [12, 3, 10, 6, 7, 4, 9, 11, 2, 8, 1, 5], [6, 10, 7, 2, 9, 12, 11, 4, 8, 3, 1, 5]]</pre>
=={{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>
=={{header|Perl 6}}==
|