Anonymous user
Permutations/Rank of a permutation: Difference between revisions
Added Perl 6
(→{{header|Julia}}: A new entry for Julia) |
(Added Perl 6) |
||
Line 647:
<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 6}}==
It is similar to Haskell, but separate something like [https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics) inversion vector].
It is easy generate random inversion vector without BigInt.
<lang perl6>use v6;
sub rank2inv ( $rank, $n = * ) {
$rank.polymod( 1 ..^ $n );
}
sub inv2rank ( @inv ) {
[+] @inv Z* [\*] 1, 1, * + 1 ... *
}
sub inv2perm ( @inv, @items is copy = ^@inv.elems ) {
my @perm;
for @inv.reverse -> $i {
@perm.append: @items.splice: $i, 1;
}
@perm;
}
sub perm2inv ( @perm ) { #not in linear time
(
{ @perm[++$ .. *].grep( * < $^cur ).elems } for @perm;
).reverse;
}
for ^6 {
my @row.push: $^rank;
for ( *.&rank2inv(3) , &inv2perm, &perm2inv, &inv2rank ) -> &code {
@row.push: code( @row[*-1] );
}
say @row;
}
my $perms = 4; #100;
my $n = 12; #144;
say 'Via BigInt rank';
for ( ( ^([*] 1 .. $n) ).pick($perms) ) {
say $^rank.&rank2inv($n).&inv2perm;
};
say 'Via inversion vectors';
for ( { my $i=0; inv2perm (^++$i).roll xx $n } ... * ).unique( with => &[eqv] ).[^$perms] {
.say;
};
say 'Via Perl 6 method pick';
for ( { [(^$n).pick(*)] } ... * ).unique( with => &[eqv] ).head($perms) {
.say
};
</lang>
{{out}}
<pre>
[0 (0 0 0) [0 1 2] (0 0 0) 0]
[1 (0 1 0) [0 2 1] (0 1 0) 1]
[2 (0 0 1) [1 0 2] (0 0 1) 2]
[3 (0 1 1) [1 2 0] (0 1 1) 3]
[4 (0 0 2) [2 0 1] (0 0 2) 4]
[5 (0 1 2) [2 1 0] (0 1 2) 5]
Via BigInt rank
[4 3 1 8 6 2 0 7 9 11 5 10]
[0 8 11 4 9 3 7 5 2 6 10 1]
[5 7 9 11 10 6 4 1 2 3 0 8]
[9 11 8 6 3 5 7 2 4 0 1 10]
Via inversion vectors
[9 0 3 1 8 2 4 5 11 7 10 6]
[7 3 1 10 0 6 4 11 2 9 8 5]
[9 8 5 11 1 10 0 7 4 6 2 3]
[10 8 6 5 4 9 0 2 11 7 1 3]
Via Perl 6 method pick
[11 0 7 10 9 4 1 8 6 5 2 3]
[4 5 8 3 2 1 7 9 11 0 10 6]
[11 7 9 4 0 8 10 1 5 2 6 3]
[11 10 0 3 4 6 7 9 8 5 1 2]
</pre>
=={{header|Python}}==
| |||