| 1 | package Math::Permutation; | ||||||||||||||||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||||||||||||||||
| 3 | 8 | ▶ | use strict; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 4 | 8 | ▶ | use warnings; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 5 | 8 | ▶ | use Carp; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 6 | 8 | ▶ | use List::Util qw/tail reduce any uniq none all sum first max min pairs mesh/; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 7 | |||||||||||||||||||||||||||||||||||||||||||
| 8 | # supportive math function | ||||||||||||||||||||||||||||||||||||||||||
| 9 | 8 | ▶ | sub _lcm { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_lcm: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 10 | 8 | ▶ | return reduce { $a*$b/_gcd($a,$b) } @_; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 11 | } | ||||||||||||||||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||||||||||||||||
| 13 | 13 | ▶ | sub _gcd { # _gcd of two positive integers | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_gcd: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||||||||||||||||
| 14 | 13 | my $x = min($_[0], $_[1]); | |||||||||||||||||||||||||||||||||||||||||
| 15 | 13 | my $y = max($_[0], $_[1]); | |||||||||||||||||||||||||||||||||||||||||
| 16 | 13 | ▶ | while ($x != 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 17 | 14 | ($x, $y) = ($y % $x, $x) | |||||||||||||||||||||||||||||||||||||||||
| 18 | } | ||||||||||||||||||||||||||||||||||||||||||
| 19 | 13 | return $y; | |||||||||||||||||||||||||||||||||||||||||
| 20 | } | ||||||||||||||||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||||||||||||||||
| 22 | 32 | ▶ | sub _factorial { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_factorial: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||||||||||||||||
| 23 | 32 | my $ans = 1; | |||||||||||||||||||||||||||||||||||||||||
| 24 | 32 | for (1..$_[0]) { | |||||||||||||||||||||||||||||||||||||||||
| 25 | 256 | $ans *= $_; | |||||||||||||||||||||||||||||||||||||||||
| 26 | } | ||||||||||||||||||||||||||||||||||||||||||
| 27 | 32 | return $ans; | |||||||||||||||||||||||||||||||||||||||||
| 28 | } | ||||||||||||||||||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||||||||||||||||
| 30 | 16 | ▶ | sub eqv { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
eqv: called CC=5 SCAR=16.5
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 31 | 16 | my $wrepr = $_[0]->{_wrepr}; | |||||||||||||||||||||||||||||||||||||||||
| 32 | 16 | my $wrepr2 = $_[1]->{_wrepr}; | |||||||||||||||||||||||||||||||||||||||||
| 33 | 16 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 34 | 16 | my $n2 = $_[1]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 35 | 16 | ▶ | return 0 if $n != $n2; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 36 | 16 | my $check = 0; | |||||||||||||||||||||||||||||||||||||||||
| 37 | 16 | for (0..$n-1) { | |||||||||||||||||||||||||||||||||||||||||
| 38 | 120 | ▶ | $check++ if $wrepr->[$_] == $wrepr2->[$_]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 39 | } | ||||||||||||||||||||||||||||||||||||||||||
| 40 | 16 | ▶ | return $check == $n ? 1 : 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 41 | } | ||||||||||||||||||||||||||||||||||||||||||
| 42 | |||||||||||||||||||||||||||||||||||||||||||
| 43 | 16 | ▶ | sub clone { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
clone: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 44 | 16 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 45 | 16 | my $wrepr = $_[1]->{_wrepr}; | |||||||||||||||||||||||||||||||||||||||||
| 46 | 16 | my $n = $_[1]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 47 | 16 | $_[0]->{_wrepr} = $wrepr; | |||||||||||||||||||||||||||||||||||||||||
| 48 | 16 | $_[0]->{_n} = $n; | |||||||||||||||||||||||||||||||||||||||||
| 49 | } | ||||||||||||||||||||||||||||||||||||||||||
| 50 | |||||||||||||||||||||||||||||||||||||||||||
| 51 | 24 | ▶ | sub init { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
init: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 52 | 24 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 53 | 24 | my $n = $_[1]; | |||||||||||||||||||||||||||||||||||||||||
| 54 | 24 | bless { | |||||||||||||||||||||||||||||||||||||||||
| 55 | _wrepr => [1..$n], | ||||||||||||||||||||||||||||||||||||||||||
| 56 | _n => $n, | ||||||||||||||||||||||||||||||||||||||||||
| 57 | }, $class; | ||||||||||||||||||||||||||||||||||||||||||
| 58 | } | ||||||||||||||||||||||||||||||||||||||||||
| 59 | |||||||||||||||||||||||||||||||||||||||||||
| 60 | 64 | ▶ | sub wrepr { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
wrepr: called CC=4 SCAR=14.8
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 61 | 64 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 62 | 64 | ▶ | my $wrepr = $_[1] || [1]; | ||||||||||||||||||||||||||||||||||||||||
|
Condition50%1/2
$_[1] || [1]
MC/DC0%0/1
$_[1] || [1]
$_[1]
Truth table50%1/2
A
A= $_[1]
| |||||||||||||||||||||||||||||||||||||||||||
| 63 | # begin: checking | ||||||||||||||||||||||||||||||||||||||||||
| 64 | 64 | my $n = scalar $wrepr->@*; | |||||||||||||||||||||||||||||||||||||||||
| 65 | 64 | my %check; | |||||||||||||||||||||||||||||||||||||||||
| 66 | 64 | $check{$_} = 1 foreach $wrepr->@*; | |||||||||||||||||||||||||||||||||||||||||
| 67 | 64 | ▶ | unless (all {defined($check{$_})} (1..$n)) { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.2
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 68 | 0 | carp "Error in input representation. " | |||||||||||||||||||||||||||||||||||||||||
| 69 | ."The permutation will initialize to identity permutation " | ||||||||||||||||||||||||||||||||||||||||||
| 70 | ."of $n elements.\n"; | ||||||||||||||||||||||||||||||||||||||||||
| 71 | 0 | $wrepr = [1..$n]; | |||||||||||||||||||||||||||||||||||||||||
| 72 | } | ||||||||||||||||||||||||||||||||||||||||||
| 73 | # end: checking | ||||||||||||||||||||||||||||||||||||||||||
| 74 | bless { | ||||||||||||||||||||||||||||||||||||||||||
| 75 | 64 | _wrepr => $wrepr, | |||||||||||||||||||||||||||||||||||||||||
| 76 | _n => $n, | ||||||||||||||||||||||||||||||||||||||||||
| 77 | }, $class; | ||||||||||||||||||||||||||||||||||||||||||
| 78 | } | ||||||||||||||||||||||||||||||||||||||||||
| 79 | |||||||||||||||||||||||||||||||||||||||||||
| 80 | 0 | ▶ | sub tabular { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
tabular: not called CC=8 SCAR=42.8
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 81 | 0 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 82 | 0 | my @domain = $_[1]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 83 | 0 | my @codomain = $_[2]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 84 | 0 | my $wrepr; | |||||||||||||||||||||||||||||||||||||||||
| 85 | 0 | my $n = scalar @domain; | |||||||||||||||||||||||||||||||||||||||||
| 86 | # begin: checking | ||||||||||||||||||||||||||||||||||||||||||
| 87 | 0 | my %check1, my %check2; | |||||||||||||||||||||||||||||||||||||||||
| 88 | 0 | $check1{$_} = 1 foreach @domain; | |||||||||||||||||||||||||||||||||||||||||
| 89 | 0 | $check2{$_} = 1 foreach @codomain; | |||||||||||||||||||||||||||||||||||||||||
| 90 | 0 | my $check = 1; | |||||||||||||||||||||||||||||||||||||||||
| 91 | 0 | ▶ | unless ( (all {defined($check1{$_})} (1..$n)) | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
Branch: 1 branch
Condition0%0/6
&all(sub {
defined $check1{$_};
}
, 1 .. $n) and $n == scalar @codomain and &all(sub {
defined $check2{$_};
}
, 1 .. $n)
&all(sub {
defined $check1{$_};
}
, 1 .. $n) and $n == scalar @codomain
MC/DC0%0/3
&all(sub {
defined $check1{$_};
}
, 1 .. $n) and $n == scalar @codomain and &all(sub {
defined $check2{$_};
}
, 1 .. $n)
&all(sub {
defined $check1{$_};
}
, 1 .. $n)
$n == scalar @codomain
&all(sub {
defined $check2{$_};
}
, 1 .. $n)
Truth table0%0/4
A and B and C
A= &all(sub {
defined $check1{$_};
}
, 1 .. $n)B= $n == scalar @codomainC= &all(sub {
defined $check2{$_};
}
, 1 .. $n)
| |||||||||||||||||||||||||||||||||||||||||||
| 92 | && $n == scalar @codomain | ||||||||||||||||||||||||||||||||||||||||||
| 93 | 0 | ▶ | && (all {defined($check2{$_})} (1..$n)) ) { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||||||||||||||||||||||
| 94 | 0 | carp "Error in input representation. " | |||||||||||||||||||||||||||||||||||||||||
| 95 | ."The permutation will initialize to identity permutation " | ||||||||||||||||||||||||||||||||||||||||||
| 96 | ."of $n elements.\n"; | ||||||||||||||||||||||||||||||||||||||||||
| 97 | 0 | $wrepr = [1..$n]; | |||||||||||||||||||||||||||||||||||||||||
| 98 | 0 | $check = 0; | |||||||||||||||||||||||||||||||||||||||||
| 99 | } | ||||||||||||||||||||||||||||||||||||||||||
| 100 | # end: checking | ||||||||||||||||||||||||||||||||||||||||||
| 101 | 0 | ▶ | if ($check) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 102 | 0 | my %w; | |||||||||||||||||||||||||||||||||||||||||
| 103 | 0 | $w{$domain[$_]} = $codomain[$_] foreach 0..$n-1; | |||||||||||||||||||||||||||||||||||||||||
| 104 | 0 | $wrepr = [ map {$w{$_}} 1..$n ]; | |||||||||||||||||||||||||||||||||||||||||
| 105 | } | ||||||||||||||||||||||||||||||||||||||||||
| 106 | bless { | ||||||||||||||||||||||||||||||||||||||||||
| 107 | 0 | _wrepr => $wrepr, | |||||||||||||||||||||||||||||||||||||||||
| 108 | _n => $n, | ||||||||||||||||||||||||||||||||||||||||||
| 109 | }, $class; | ||||||||||||||||||||||||||||||||||||||||||
| 110 | } | ||||||||||||||||||||||||||||||||||||||||||
| 111 | |||||||||||||||||||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||||||||||||||||
| 113 | 2 | ▶ | sub cycles { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
cycles: called CC=13 SCAR=36.7
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 114 | 2 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 115 | 2 | my @cycles = $_[1]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 116 | 2 | my $wrepr; | |||||||||||||||||||||||||||||||||||||||||
| 117 | my @elements; | ||||||||||||||||||||||||||||||||||||||||||
| 118 | 2 | push @elements, @{$_} foreach @cycles; | |||||||||||||||||||||||||||||||||||||||||
| 119 | 2 | my $n = int max @elements; | |||||||||||||||||||||||||||||||||||||||||
| 120 | # begin: checking | ||||||||||||||||||||||||||||||||||||||||||
| 121 | 2 | my $check = 1; | |||||||||||||||||||||||||||||||||||||||||
| 122 | 2 | for (@elements) { | |||||||||||||||||||||||||||||||||||||||||
| 123 | 2 | ▶ | if ($_ != int $_ || $_ <= 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$_ != int $_ or $_ <= 0
MC/DC0%0/2
$_ != int $_ or $_ <= 0
$_ != int $_
$_ <= 0
Truth table33%1/3
A or B
A= $_ != int $_B= $_ <= 0
| |||||||||||||||||||||||||||||||||||||||||||
| 124 | 0 | $check = 0; | |||||||||||||||||||||||||||||||||||||||||
| 125 | 0 | last; | |||||||||||||||||||||||||||||||||||||||||
| 126 | } | ||||||||||||||||||||||||||||||||||||||||||
| 127 | } | ||||||||||||||||||||||||||||||||||||||||||
| 128 | 2 | for (@cycles) { | |||||||||||||||||||||||||||||||||||||||||
| 129 | 2 | ▶ | if ((scalar uniq @{$_}) != (scalar @{$_})) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 130 | 0 | $check = 0; | |||||||||||||||||||||||||||||||||||||||||
| 131 | 0 | last; | |||||||||||||||||||||||||||||||||||||||||
| 132 | } | ||||||||||||||||||||||||||||||||||||||||||
| 133 | } | ||||||||||||||||||||||||||||||||||||||||||
| 134 | 2 | ▶ | if (!$check) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 135 | 0 | carp "Error in input representation. " | |||||||||||||||||||||||||||||||||||||||||
| 136 | ."The permutation will initialize to identity permutation " | ||||||||||||||||||||||||||||||||||||||||||
| 137 | ."of $n elements.\n"; | ||||||||||||||||||||||||||||||||||||||||||
| 138 | 0 | $wrepr = [1..$n]; | |||||||||||||||||||||||||||||||||||||||||
| 139 | } | ||||||||||||||||||||||||||||||||||||||||||
| 140 | # end: checking | ||||||||||||||||||||||||||||||||||||||||||
| 141 | 2 | ▶ | if ($check) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 142 | 2 | ▶ | if ((scalar uniq @elements) == (scalar @elements)) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 143 | 2 | $wrepr = _cycles_to_wrepr($n, [@cycles]); | |||||||||||||||||||||||||||||||||||||||||
| 144 | } | ||||||||||||||||||||||||||||||||||||||||||
| 145 | else { | ||||||||||||||||||||||||||||||||||||||||||
| 146 | # composition operation | ||||||||||||||||||||||||||||||||||||||||||
| 147 | 0 | my @ws; | |||||||||||||||||||||||||||||||||||||||||
| 148 | 0 | @ws = map {_cycles_to_wrepr($n, [ $_ ] ) } @cycles; | |||||||||||||||||||||||||||||||||||||||||
| 149 | 0 | my @qp; | |||||||||||||||||||||||||||||||||||||||||
| 150 | 0 | my @p = $ws[-1]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 151 | 0 | for my $j (2..scalar @cycles) { | |||||||||||||||||||||||||||||||||||||||||
| 152 | 0 | @qp = (); | |||||||||||||||||||||||||||||||||||||||||
| 153 | 0 | my @q = $ws[-$j]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 154 | 0 | push @qp, $q[$p[$_-1]-1] for 1..$n; | |||||||||||||||||||||||||||||||||||||||||
| 155 | 0 | @p = @qp; | |||||||||||||||||||||||||||||||||||||||||
| 156 | } | ||||||||||||||||||||||||||||||||||||||||||
| 157 | 0 | ▶ | @qp = map { $qp[$_] == 0 ? $_+1 : $qp[$_] } (0..$n-1); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 158 | 0 | $wrepr = [@qp]; | |||||||||||||||||||||||||||||||||||||||||
| 159 | } | ||||||||||||||||||||||||||||||||||||||||||
| 160 | } | ||||||||||||||||||||||||||||||||||||||||||
| 161 | bless { | ||||||||||||||||||||||||||||||||||||||||||
| 162 | 2 | _wrepr => $wrepr, | |||||||||||||||||||||||||||||||||||||||||
| 163 | _n => $n, | ||||||||||||||||||||||||||||||||||||||||||
| 164 | }, $class; | ||||||||||||||||||||||||||||||||||||||||||
| 165 | } | ||||||||||||||||||||||||||||||||||||||||||
| 166 | |||||||||||||||||||||||||||||||||||||||||||
| 167 | 10 | ▶ | sub _cycles_to_wrepr { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_cycles_to_wrepr: called CC=7 SCAR=19.5
| |||||||||||||||||||||||||||||||||||||||||||
| 168 | 10 | my $n = $_[0]; | |||||||||||||||||||||||||||||||||||||||||
| 169 | 10 | my @cycles = $_[1]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 170 | 10 | my %hash; | |||||||||||||||||||||||||||||||||||||||||
| 171 | 10 | $hash{$_} = 0 for (1..$n); | |||||||||||||||||||||||||||||||||||||||||
| 172 | 10 | for my $c (@cycles) { | |||||||||||||||||||||||||||||||||||||||||
| 173 | 24 | ▶ | if (scalar @{$c} > 1) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 174 | 14 | $hash{$c->[$_]} = $c->[$_+1] for (0..scalar @{$c} - 2); | |||||||||||||||||||||||||||||||||||||||||
| 175 | 14 | $hash{$c->[-1]} = $c->[0]; | |||||||||||||||||||||||||||||||||||||||||
| 176 | } | ||||||||||||||||||||||||||||||||||||||||||
| 177 | 10 | elsif (scalar @{$c} == 1) { | |||||||||||||||||||||||||||||||||||||||||
| 178 | 10 | $hash{$c->[0]} = $c->[0]; | |||||||||||||||||||||||||||||||||||||||||
| 179 | } | ||||||||||||||||||||||||||||||||||||||||||
| 180 | } | ||||||||||||||||||||||||||||||||||||||||||
| 181 | 10 | ▶ | return [ map {$hash{$_} == 0 ? $_ : $hash{$_}} (1..$n) ]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 182 | } | ||||||||||||||||||||||||||||||||||||||||||
| 183 | |||||||||||||||||||||||||||||||||||||||||||
| 184 | 2 | ▶ | sub cycles_with_len { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
cycles_with_len: called CC=3 SCAR=11.8
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 185 | 2 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 186 | 2 | my $n = $_[1]; | |||||||||||||||||||||||||||||||||||||||||
| 187 | 2 | my @cycles = $_[2]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 188 | 2 | my @elements; | |||||||||||||||||||||||||||||||||||||||||
| 189 | 0 | push @elements, @{$_} foreach @cycles; | |||||||||||||||||||||||||||||||||||||||||
| 190 | 0 | ▶ | return (any {$n == $_} @elements) ? $_[0]->cycles([@cycles]) | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=1.2
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 191 | : $_[0]->cycles([@cycles, [$n]]); | ||||||||||||||||||||||||||||||||||||||||||
| 192 | } | ||||||||||||||||||||||||||||||||||||||||||
| 193 | |||||||||||||||||||||||||||||||||||||||||||
| 194 | 0 | ▶ | sub sprint_wrepr { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
sprint_wrepr: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 195 | 0 | return "\"" . (join ",", $_[0]->{_wrepr}->@*) . "\""; | |||||||||||||||||||||||||||||||||||||||||
| 196 | } | ||||||||||||||||||||||||||||||||||||||||||
| 197 | |||||||||||||||||||||||||||||||||||||||||||
| 198 | 0 | ▶ | sub sprint_tabular { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
sprint_tabular: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 199 | 0 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 200 | 0 | my $digit_len = length $n; | |||||||||||||||||||||||||||||||||||||||||
| 201 | return | ||||||||||||||||||||||||||||||||||||||||||
| 202 | 0 | "|" . (join " ", map {sprintf("%*s", $digit_len, $_)} 1..$n ) | |||||||||||||||||||||||||||||||||||||||||
| 203 | . "|" . "\n" | ||||||||||||||||||||||||||||||||||||||||||
| 204 | ."|" | ||||||||||||||||||||||||||||||||||||||||||
| 205 | 0 | . (join " ", map {sprintf("%*s", $digit_len, $_)} $_[0]->{_wrepr}->@* ) | |||||||||||||||||||||||||||||||||||||||||
| 206 | 0 | . "|"; | |||||||||||||||||||||||||||||||||||||||||
| 207 | } | ||||||||||||||||||||||||||||||||||||||||||
| 208 | |||||||||||||||||||||||||||||||||||||||||||
| 209 | 0 | ▶ | sub sprint_cycles { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
sprint_cycles: not called CC=2 SCAR=17.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 210 | 0 | my @cycles = $_[0]->cyc->@*; | |||||||||||||||||||||||||||||||||||||||||
| 211 | 0 | @cycles = grep { scalar @{$_} > 1 } @cycles; | |||||||||||||||||||||||||||||||||||||||||
| 212 | 0 | ▶ | return "()" if scalar @cycles == 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 213 | 0 | my @p_cycles = map {"(".(join " ", @{$_}). ")"} @cycles; | |||||||||||||||||||||||||||||||||||||||||
| 214 | 0 | return join " ", @p_cycles; | |||||||||||||||||||||||||||||||||||||||||
| 215 | } | ||||||||||||||||||||||||||||||||||||||||||
| 216 | |||||||||||||||||||||||||||||||||||||||||||
| 217 | 0 | ▶ | sub sprint_cycles_full { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
sprint_cycles_full: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 218 | 0 | my @cycles = $_[0]->cyc->@*; | |||||||||||||||||||||||||||||||||||||||||
| 219 | 0 | my @p_cycles = map {"(".(join " ", @{$_}). ")"} @cycles; | |||||||||||||||||||||||||||||||||||||||||
| 220 | 0 | return join " ", @p_cycles; | |||||||||||||||||||||||||||||||||||||||||
| 221 | } | ||||||||||||||||||||||||||||||||||||||||||
| 222 | |||||||||||||||||||||||||||||||||||||||||||
| 223 | 0 | ▶ | sub array { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
array: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 224 | 0 | return $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 225 | } | ||||||||||||||||||||||||||||||||||||||||||
| 226 | |||||||||||||||||||||||||||||||||||||||||||
| 227 | 65 | ▶ | sub swap { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
swap: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 228 | 65 | my $i = $_[1]; | |||||||||||||||||||||||||||||||||||||||||
| 229 | 65 | my $j = $_[2]; | |||||||||||||||||||||||||||||||||||||||||
| 230 | 65 | my $wrepr = $_[0]->{_wrepr}; | |||||||||||||||||||||||||||||||||||||||||
| 231 | 65 | ($wrepr->[$i-1], $wrepr->[$j-1]) = ($wrepr->[$j-1], $wrepr->[$i-1]); | |||||||||||||||||||||||||||||||||||||||||
| 232 | 65 | $_[0]->{_wrepr} = $wrepr; | |||||||||||||||||||||||||||||||||||||||||
| 233 | 65 | return $_[0]; | |||||||||||||||||||||||||||||||||||||||||
| 234 | } | ||||||||||||||||||||||||||||||||||||||||||
| 235 | |||||||||||||||||||||||||||||||||||||||||||
| 236 | 28 | ▶ | sub comp { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
comp: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 237 | 28 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 238 | 28 | my @p = $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 239 | 28 | my @q = $_[1]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 240 | 28 | ▶ | return [] if scalar @q != $n; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 241 | 28 | my @qp; | |||||||||||||||||||||||||||||||||||||||||
| 242 | 28 | push @qp, $q[$p[$_-1]-1] for 1..$n; | |||||||||||||||||||||||||||||||||||||||||
| 243 | 28 | $_[0]->{_wrepr} = [@qp]; | |||||||||||||||||||||||||||||||||||||||||
| 244 | 28 | return $_[0]; | |||||||||||||||||||||||||||||||||||||||||
| 245 | } | ||||||||||||||||||||||||||||||||||||||||||
| 246 | |||||||||||||||||||||||||||||||||||||||||||
| 247 | 8 | ▶ | sub inverse { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
inverse: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 248 | 8 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 249 | 8 | my @cycles = $_[0]->cyc->@*; | |||||||||||||||||||||||||||||||||||||||||
| 250 | 8 | my @new_cycles; | |||||||||||||||||||||||||||||||||||||||||
| 251 | 8 | foreach (@cycles) { | |||||||||||||||||||||||||||||||||||||||||
| 252 | 22 | push @new_cycles, [reverse @{$_}]; | |||||||||||||||||||||||||||||||||||||||||
| 253 | } | ||||||||||||||||||||||||||||||||||||||||||
| 254 | 8 | $_[0]->{_wrepr} = _cycles_to_wrepr($n, [@new_cycles]); | |||||||||||||||||||||||||||||||||||||||||
| 255 | 8 | return $_[0]; | |||||||||||||||||||||||||||||||||||||||||
| 256 | } | ||||||||||||||||||||||||||||||||||||||||||
| 257 | |||||||||||||||||||||||||||||||||||||||||||
| 258 | 8 | ▶ | sub nxt { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
nxt: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 259 | 8 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 260 | 8 | my @w = $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 261 | 8 | my @rw = reverse @w; | |||||||||||||||||||||||||||||||||||||||||
| 262 | 8 | my $ind = 1; | |||||||||||||||||||||||||||||||||||||||||
| 263 | 8 | ▶ | while ($ind <= $#rw && $rw[$ind-1] < $rw[$ind]) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$ind <= $#rw and $rw[$ind - 1] < $rw[$ind]
MC/DC50%1/2
$ind <= $#rw and $rw[$ind - 1] < $rw[$ind]
$ind <= $#rw
$rw[$ind - 1] < $rw[$ind]
Truth table66%2/3
A and B
A= $ind <= $#rwB= $rw[$ind - 1] < $rw[$ind]
| |||||||||||||||||||||||||||||||||||||||||||
| 264 | 6 | $ind++; | |||||||||||||||||||||||||||||||||||||||||
| 265 | } | ||||||||||||||||||||||||||||||||||||||||||
| 266 | 8 | ▶ | return [] if $ind == scalar @w; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 267 | 8 | my @suffix = tail $ind, @w; | |||||||||||||||||||||||||||||||||||||||||
| 268 | 8 | my $i = 1; | |||||||||||||||||||||||||||||||||||||||||
| 269 | 8 | ▶ | $i++ until $w[-$ind-1] < $suffix[-$i]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 270 | 8 | ($w[-$ind-1], $suffix[-$i]) = ($suffix[-$i], $w[-$ind-1]); | |||||||||||||||||||||||||||||||||||||||||
| 271 | 8 | $_[0]->{_wrepr} = [ @w[0..$n-$ind-1], reverse @suffix ]; | |||||||||||||||||||||||||||||||||||||||||
| 272 | 8 | return $_[0]; | |||||||||||||||||||||||||||||||||||||||||
| 273 | } | ||||||||||||||||||||||||||||||||||||||||||
| 274 | |||||||||||||||||||||||||||||||||||||||||||
| 275 | 8 | ▶ | sub prev { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
prev: called CC=5 SCAR=16.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 276 | 8 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 277 | 8 | my @w = $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 278 | 8 | my @rw = reverse @w; | |||||||||||||||||||||||||||||||||||||||||
| 279 | 8 | my $ind = 1; | |||||||||||||||||||||||||||||||||||||||||
| 280 | 8 | ▶ | while ($ind <= $#rw && $rw[$ind-1] > $rw[$ind]) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$ind <= $#rw and $rw[$ind - 1] > $rw[$ind]
MC/DC50%1/2
$ind <= $#rw and $rw[$ind - 1] > $rw[$ind]
$ind <= $#rw
$rw[$ind - 1] > $rw[$ind]
Truth table66%2/3
A and B
A= $ind <= $#rwB= $rw[$ind - 1] > $rw[$ind]
| |||||||||||||||||||||||||||||||||||||||||||
| 281 | 6 | $ind++; | |||||||||||||||||||||||||||||||||||||||||
| 282 | } | ||||||||||||||||||||||||||||||||||||||||||
| 283 | 8 | ▶ | return [] if $ind == scalar @w; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 284 | 8 | my @suffix = tail $ind, @w; | |||||||||||||||||||||||||||||||||||||||||
| 285 | 8 | my $i = 1; | |||||||||||||||||||||||||||||||||||||||||
| 286 | 8 | ▶ | $i++ until $w[-$ind-1] > $suffix[-$i]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 287 | 8 | ($w[-$ind-1], $suffix[-$i]) = ($suffix[-$i], $w[-$ind-1]); | |||||||||||||||||||||||||||||||||||||||||
| 288 | 8 | $_[0]->{_wrepr} = [ @w[0..$n-$ind-1], reverse @suffix ]; | |||||||||||||||||||||||||||||||||||||||||
| 289 | 8 | return $_[0]; | |||||||||||||||||||||||||||||||||||||||||
| 290 | } | ||||||||||||||||||||||||||||||||||||||||||
| 291 | |||||||||||||||||||||||||||||||||||||||||||
| 292 | 0 | ▶ | sub unrank { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
unrank: not called CC=3 SCAR=24.8
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 293 | 0 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 294 | 0 | my $n = $_[1]; | |||||||||||||||||||||||||||||||||||||||||
| 295 | 0 | my @list = (1..$n); | |||||||||||||||||||||||||||||||||||||||||
| 296 | 0 | my $r = $_[2]-1; | |||||||||||||||||||||||||||||||||||||||||
| 297 | 0 | my $fact = _factorial($n-1); | |||||||||||||||||||||||||||||||||||||||||
| 298 | 0 | my @unused_list = sort {$a<=>$b} @list; | |||||||||||||||||||||||||||||||||||||||||
| 299 | 0 | my @p = (); | |||||||||||||||||||||||||||||||||||||||||
| 300 | 0 | for my $i (0..$n-1) { | |||||||||||||||||||||||||||||||||||||||||
| 301 | 0 | my $q = int $r / $fact; | |||||||||||||||||||||||||||||||||||||||||
| 302 | 0 | $r %= $fact; | |||||||||||||||||||||||||||||||||||||||||
| 303 | 0 | push @p, $unused_list[$q]; | |||||||||||||||||||||||||||||||||||||||||
| 304 | 0 | splice @unused_list, $q, 1; | |||||||||||||||||||||||||||||||||||||||||
| 305 | 0 | ▶ | $fact = int $fact / ($n-1-$i) if $i != $n-1; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 306 | } | ||||||||||||||||||||||||||||||||||||||||||
| 307 | 0 | my $wrepr = [@p]; | |||||||||||||||||||||||||||||||||||||||||
| 308 | 0 | bless { | |||||||||||||||||||||||||||||||||||||||||
| 309 | _wrepr => $wrepr, | ||||||||||||||||||||||||||||||||||||||||||
| 310 | _n => $n, | ||||||||||||||||||||||||||||||||||||||||||
| 311 | }, $class; | ||||||||||||||||||||||||||||||||||||||||||
| 312 | } | ||||||||||||||||||||||||||||||||||||||||||
| 313 | |||||||||||||||||||||||||||||||||||||||||||
| 314 | # Fisher-Yates shuffle | ||||||||||||||||||||||||||||||||||||||||||
| 315 | 32 | ▶ | sub random { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
random: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 316 | 32 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 317 | 32 | my $n = $_[1]; | |||||||||||||||||||||||||||||||||||||||||
| 318 | 32 | my @ori = (1..$n); | |||||||||||||||||||||||||||||||||||||||||
| 319 | 32 | my @w; | |||||||||||||||||||||||||||||||||||||||||
| 320 | 32 | for (1..$n) { | |||||||||||||||||||||||||||||||||||||||||
| 321 | 264 | my $roll = int (rand() * scalar @ori); | |||||||||||||||||||||||||||||||||||||||||
| 322 | 264 | push @w, $ori[$roll]; | |||||||||||||||||||||||||||||||||||||||||
| 323 | 264 | ($ori[$roll], $ori[-1]) = ($ori[-1], $ori[$roll]); | |||||||||||||||||||||||||||||||||||||||||
| 324 | 264 | pop @ori; | |||||||||||||||||||||||||||||||||||||||||
| 325 | } | ||||||||||||||||||||||||||||||||||||||||||
| 326 | bless { | ||||||||||||||||||||||||||||||||||||||||||
| 327 | 32 | _wrepr => [@w], | |||||||||||||||||||||||||||||||||||||||||
| 328 | _n => $n, | ||||||||||||||||||||||||||||||||||||||||||
| 329 | }, $class; | ||||||||||||||||||||||||||||||||||||||||||
| 330 | } | ||||||||||||||||||||||||||||||||||||||||||
| 331 | |||||||||||||||||||||||||||||||||||||||||||
| 332 | 24 | ▶ | sub cyc { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
cyc: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 333 | 24 | my $w = $_[0]->{_wrepr}; | |||||||||||||||||||||||||||||||||||||||||
| 334 | 24 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 335 | 24 | my %hash; | |||||||||||||||||||||||||||||||||||||||||
| 336 | 24 | $hash{$_} = $w->[$_-1] foreach 1..$n; | |||||||||||||||||||||||||||||||||||||||||
| 337 | 24 | my @cycles; | |||||||||||||||||||||||||||||||||||||||||
| 338 | 24 | ▶ | while (scalar %hash != 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 339 | 102 | ▶ | my $c1 = first {1} %hash; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 340 | 102 | my @cycle; | |||||||||||||||||||||||||||||||||||||||||
| 341 | 102 | my $c = $c1; | |||||||||||||||||||||||||||||||||||||||||
| 342 | 102 | ▶ | do { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 343 | 184 | push @cycle, $c; | |||||||||||||||||||||||||||||||||||||||||
| 344 | 184 | my $pre_c = $c; | |||||||||||||||||||||||||||||||||||||||||
| 345 | 184 | $c = $hash{$c}; | |||||||||||||||||||||||||||||||||||||||||
| 346 | 184 | delete $hash{$pre_c}; | |||||||||||||||||||||||||||||||||||||||||
| 347 | } while ($c != $c1); | ||||||||||||||||||||||||||||||||||||||||||
| 348 | 102 | push @cycles, [@cycle]; | |||||||||||||||||||||||||||||||||||||||||
| 349 | } | ||||||||||||||||||||||||||||||||||||||||||
| 350 | 24 | return [@cycles]; | |||||||||||||||||||||||||||||||||||||||||
| 351 | } | ||||||||||||||||||||||||||||||||||||||||||
| 352 | |||||||||||||||||||||||||||||||||||||||||||
| 353 | |||||||||||||||||||||||||||||||||||||||||||
| 354 | |||||||||||||||||||||||||||||||||||||||||||
| 355 | 0 | ▶ | sub sigma { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
sigma: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 356 | 0 | return $_[0]->{_wrepr}->[$_[1]-1]; | |||||||||||||||||||||||||||||||||||||||||
| 357 | } | ||||||||||||||||||||||||||||||||||||||||||
| 358 | |||||||||||||||||||||||||||||||||||||||||||
| 359 | 0 | ▶ | sub rule { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
rule: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 360 | 0 | return $_[0]->{_wrepr}; | |||||||||||||||||||||||||||||||||||||||||
| 361 | } | ||||||||||||||||||||||||||||||||||||||||||
| 362 | |||||||||||||||||||||||||||||||||||||||||||
| 363 | 0 | ▶ | sub elems { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
elems: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 364 | 0 | return $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 365 | } | ||||||||||||||||||||||||||||||||||||||||||
| 366 | |||||||||||||||||||||||||||||||||||||||||||
| 367 | 32 | ▶ | sub rank { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
rank: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 368 | 32 | my @list = $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 369 | 32 | my $n = scalar @list; | |||||||||||||||||||||||||||||||||||||||||
| 370 | 32 | my $fact = _factorial($n-1); | |||||||||||||||||||||||||||||||||||||||||
| 371 | 32 | my $r = 1; | |||||||||||||||||||||||||||||||||||||||||
| 372 | 32 | my @unused_list = sort {$a<=>$b} @list; | |||||||||||||||||||||||||||||||||||||||||
| 373 | 32 | for my $i (0..$n-2) { | |||||||||||||||||||||||||||||||||||||||||
| 374 | 256 | ▶ | my $q = first { $unused_list[$_] == $list[$i] } 0..$#unused_list; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 375 | 256 | $r += $q*$fact; | |||||||||||||||||||||||||||||||||||||||||
| 376 | 256 | splice @unused_list, $q, 1; | |||||||||||||||||||||||||||||||||||||||||
| 377 | 256 | $fact = int $fact / ($n-$i-1); | |||||||||||||||||||||||||||||||||||||||||
| 378 | } | ||||||||||||||||||||||||||||||||||||||||||
| 379 | 32 | return $r; | |||||||||||||||||||||||||||||||||||||||||
| 380 | } | ||||||||||||||||||||||||||||||||||||||||||
| 381 | |||||||||||||||||||||||||||||||||||||||||||
| 382 | # rank() and unrank($n, $i) using | ||||||||||||||||||||||||||||||||||||||||||
| 383 | # O(n^2) solution, translation of Python code on | ||||||||||||||||||||||||||||||||||||||||||
| 384 | # https://tryalgo.org/en/permutations/2016/09/05/permutation-rank/ | ||||||||||||||||||||||||||||||||||||||||||
| 385 | |||||||||||||||||||||||||||||||||||||||||||
| 386 | 0 | ▶ | sub index { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
index: not called CC=3 SCAR=24.8
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 387 | 0 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 388 | 0 | my @w = $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 389 | 0 | my $ans = 0; | |||||||||||||||||||||||||||||||||||||||||
| 390 | 0 | for my $j (0..$n-2) { | |||||||||||||||||||||||||||||||||||||||||
| 391 | 0 | ▶ | $ans += ($j+1) if $w[$j] > $w[$j+1]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 392 | } | ||||||||||||||||||||||||||||||||||||||||||
| 393 | 0 | return $ans; | |||||||||||||||||||||||||||||||||||||||||
| 394 | } | ||||||||||||||||||||||||||||||||||||||||||
| 395 | |||||||||||||||||||||||||||||||||||||||||||
| 396 | 8 | ▶ | sub order { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
order: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 397 | 8 | my @cycles = $_[0]->cyc->@*; | |||||||||||||||||||||||||||||||||||||||||
| 398 | 8 | return _lcm(map {scalar @{$_}} @cycles); | |||||||||||||||||||||||||||||||||||||||||
| 399 | } | ||||||||||||||||||||||||||||||||||||||||||
| 400 | |||||||||||||||||||||||||||||||||||||||||||
| 401 | 8 | ▶ | sub is_even { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
is_even: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 402 | 8 | my @cycles = $_[0]->cyc->@*; | |||||||||||||||||||||||||||||||||||||||||
| 403 | 8 | my $num_of_two_swaps = sum(map { scalar @{$_} - 1 } @cycles); | |||||||||||||||||||||||||||||||||||||||||
| 404 | 8 | ▶ | return $num_of_two_swaps % 2 == 0 ? 1 : 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 405 | } | ||||||||||||||||||||||||||||||||||||||||||
| 406 | |||||||||||||||||||||||||||||||||||||||||||
| 407 | 8 | ▶ | sub is_odd { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
is_odd: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 408 | 8 | ▶ | return $_[0]->is_even ? 0 : 1; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 409 | } | ||||||||||||||||||||||||||||||||||||||||||
| 410 | |||||||||||||||||||||||||||||||||||||||||||
| 411 | 0 | ▶ | sub sgn { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
sgn: not called CC=2 SCAR=17.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 412 | 0 | ▶ | return $_[0]->is_even ? 1 : -1; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 413 | } | ||||||||||||||||||||||||||||||||||||||||||
| 414 | |||||||||||||||||||||||||||||||||||||||||||
| 415 | 24 | ▶ | sub inversion { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
inversion: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 416 | 24 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 417 | 24 | my @w = $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 418 | 24 | my @inv; | |||||||||||||||||||||||||||||||||||||||||
| 419 | 24 | for my $k (1..$n) { | |||||||||||||||||||||||||||||||||||||||||
| 420 | 96 | my $i = 0; | |||||||||||||||||||||||||||||||||||||||||
| 421 | 96 | my $j = 0; | |||||||||||||||||||||||||||||||||||||||||
| 422 | 96 | ▶ | while ($w[$j] != $k) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 423 | 144 | ▶ | $i++ if $w[$j] > $k; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 424 | 144 | $j++; | |||||||||||||||||||||||||||||||||||||||||
| 425 | } | ||||||||||||||||||||||||||||||||||||||||||
| 426 | 96 | push @inv, $i; | |||||||||||||||||||||||||||||||||||||||||
| 427 | } | ||||||||||||||||||||||||||||||||||||||||||
| 428 | 24 | return [@inv]; | |||||||||||||||||||||||||||||||||||||||||
| 429 | } | ||||||||||||||||||||||||||||||||||||||||||
| 430 | |||||||||||||||||||||||||||||||||||||||||||
| 431 | 0 | ▶ | sub matrix { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
matrix: not called CC=4 SCAR=30.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 432 | 0 | my $mat; | |||||||||||||||||||||||||||||||||||||||||
| 433 | 0 | my $n = $_[0]->{_n}; | |||||||||||||||||||||||||||||||||||||||||
| 434 | 0 | my @w = $_[0]->{_wrepr}->@*; | |||||||||||||||||||||||||||||||||||||||||
| 435 | 0 | for my $i (0..$n-1) { | |||||||||||||||||||||||||||||||||||||||||
| 436 | 0 | for my $j (0..$n-1) { | |||||||||||||||||||||||||||||||||||||||||
| 437 | 0 | $mat->[$i]->[$j] = 0; | |||||||||||||||||||||||||||||||||||||||||
| 438 | } | ||||||||||||||||||||||||||||||||||||||||||
| 439 | } | ||||||||||||||||||||||||||||||||||||||||||
| 440 | 0 | $mat->[$w[$_]-1]->[$_] = 1 for (0..$n-1); | |||||||||||||||||||||||||||||||||||||||||
| 441 | 0 | return $mat; | |||||||||||||||||||||||||||||||||||||||||
| 442 | } | ||||||||||||||||||||||||||||||||||||||||||
| 443 | |||||||||||||||||||||||||||||||||||||||||||
| 444 | 40 | ▶ | sub fixed_points { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
fixed_points: called CC=3 SCAR=11.1
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 445 | 40 | my @fp; | |||||||||||||||||||||||||||||||||||||||||
| 446 | 40 | for (1..$_[0]->{_n}) { | |||||||||||||||||||||||||||||||||||||||||
| 447 | 184 | ▶ | push @fp, $_ if $_[0]->{_wrepr}->[$_-1] == $_; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 448 | } | ||||||||||||||||||||||||||||||||||||||||||
| 449 | 40 | return [@fp]; | |||||||||||||||||||||||||||||||||||||||||
| 450 | } | ||||||||||||||||||||||||||||||||||||||||||
| 451 | |||||||||||||||||||||||||||||||||||||||||||
| 452 | 0 | ▶ | sub _reorder_odd_cycle { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_reorder_odd_cycle: not called CC=2 SCAR=17.9
| |||||||||||||||||||||||||||||||||||||||||||
| 453 | 0 | my @arr = @_; | |||||||||||||||||||||||||||||||||||||||||
| 454 | 0 | my @ans; | |||||||||||||||||||||||||||||||||||||||||
| 455 | 0 | my $m = $#arr / 2; | |||||||||||||||||||||||||||||||||||||||||
| 456 | 0 | for (0..$m-1) { | |||||||||||||||||||||||||||||||||||||||||
| 457 | 0 | push @ans, $arr[$_], $arr[$m+$_+1]; | |||||||||||||||||||||||||||||||||||||||||
| 458 | } | ||||||||||||||||||||||||||||||||||||||||||
| 459 | 0 | push @ans, $arr[$m]; | |||||||||||||||||||||||||||||||||||||||||
| 460 | 0 | return @ans; | |||||||||||||||||||||||||||||||||||||||||
| 461 | } | ||||||||||||||||||||||||||||||||||||||||||
| 462 | |||||||||||||||||||||||||||||||||||||||||||
| 463 | 0 | ▶ | sub sqrt { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
sqrt: not called CC=9 SCAR=45.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 464 | 0 | my ($class) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 465 | 0 | my @new_cycles; | |||||||||||||||||||||||||||||||||||||||||
| 466 | 0 | my @cycles = $_[0]->cyc->@*; | |||||||||||||||||||||||||||||||||||||||||
| 467 | 0 | my %odd_cycle; | |||||||||||||||||||||||||||||||||||||||||
| 468 | my %even_cycle; | ||||||||||||||||||||||||||||||||||||||||||
| 469 | 0 | for my $i (0..$#cycles) { | |||||||||||||||||||||||||||||||||||||||||
| 470 | 0 | ▶ | if (scalar $cycles[$i]->@* % 2 == 1) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 471 | 0 | $odd_cycle{$i} = 1; | |||||||||||||||||||||||||||||||||||||||||
| 472 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 473 | 0 | $even_cycle{$i} = scalar $cycles[$i]->@*; | |||||||||||||||||||||||||||||||||||||||||
| 474 | } | ||||||||||||||||||||||||||||||||||||||||||
| 475 | } | ||||||||||||||||||||||||||||||||||||||||||
| 476 | 0 | ▶ | if ((scalar (values %even_cycle) % 2) == 0) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 477 | 0 | my @epairs = pairs sort {$a<=>$b} values %even_cycle; | |||||||||||||||||||||||||||||||||||||||||
| 478 | 0 | for (@epairs) { | |||||||||||||||||||||||||||||||||||||||||
| 479 | 0 | ▶ | if ($_->[0] != $_->[1]) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 480 | 0 | return undef; | |||||||||||||||||||||||||||||||||||||||||
| 481 | } | ||||||||||||||||||||||||||||||||||||||||||
| 482 | } | ||||||||||||||||||||||||||||||||||||||||||
| 483 | 0 | for my $i (keys %odd_cycle) { | |||||||||||||||||||||||||||||||||||||||||
| 484 | 0 | push @new_cycles, [_reorder_odd_cycle($cycles[$i]->@*)]; | |||||||||||||||||||||||||||||||||||||||||
| 485 | } | ||||||||||||||||||||||||||||||||||||||||||
| 486 | 0 | my @tol = keys %even_cycle; | |||||||||||||||||||||||||||||||||||||||||
| 487 | 0 | for my $i (@tol) { | |||||||||||||||||||||||||||||||||||||||||
| 488 | 0 | ▶ | next if !defined($even_cycle{$i}); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 489 | 0 | ▶ | my $j = first {$even_cycle{$_} == $even_cycle{$i} && $_ != $i} keys %even_cycle; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=2 SCAR=17.9
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 490 | 0 | delete $even_cycle{$j}; | |||||||||||||||||||||||||||||||||||||||||
| 491 | 0 | push @new_cycles, [ mesh($cycles[$i], $cycles[$j]) ]; | |||||||||||||||||||||||||||||||||||||||||
| 492 | 0 | delete $even_cycle{$i}; | |||||||||||||||||||||||||||||||||||||||||
| 493 | } | ||||||||||||||||||||||||||||||||||||||||||
| 494 | } | ||||||||||||||||||||||||||||||||||||||||||
| 495 | else { | ||||||||||||||||||||||||||||||||||||||||||
| 496 | 0 | return undef; | |||||||||||||||||||||||||||||||||||||||||
| 497 | } | ||||||||||||||||||||||||||||||||||||||||||
| 498 | 0 | return Math::Permutation->cycles([@new_cycles]); | |||||||||||||||||||||||||||||||||||||||||
| 499 | } | ||||||||||||||||||||||||||||||||||||||||||
| 500 | |||||||||||||||||||||||||||||||||||||||||||
| 501 | |||||||||||||||||||||||||||||||||||||||||||
| 502 | =head1 NAME | ||||||||||||||||||||||||||||||||||||||||||
| 503 | |||||||||||||||||||||||||||||||||||||||||||
| 504 | Math::Permutation - pure Perl implementation of functions related to the permutations | ||||||||||||||||||||||||||||||||||||||||||
| 505 | |||||||||||||||||||||||||||||||||||||||||||
| 506 | =head1 VERSION | ||||||||||||||||||||||||||||||||||||||||||
| 507 | |||||||||||||||||||||||||||||||||||||||||||
| 508 | Version 0.0212 | ||||||||||||||||||||||||||||||||||||||||||
| 509 | |||||||||||||||||||||||||||||||||||||||||||
| 510 | =cut | ||||||||||||||||||||||||||||||||||||||||||
| 511 | |||||||||||||||||||||||||||||||||||||||||||
| 512 | 8 | our $VERSION = '0.0212'; | |||||||||||||||||||||||||||||||||||||||||
| 513 | |||||||||||||||||||||||||||||||||||||||||||
| 514 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||||||||||||||||
| 515 | |||||||||||||||||||||||||||||||||||||||||||
| 516 | use Math::Permutation; | ||||||||||||||||||||||||||||||||||||||||||
| 517 | |||||||||||||||||||||||||||||||||||||||||||
| 518 | my $foo = Math::Permutation->cycles([[1,2,6,7], [3,4,5]]); | ||||||||||||||||||||||||||||||||||||||||||
| 519 | say $foo->sprint_wrepr; | ||||||||||||||||||||||||||||||||||||||||||
| 520 | # "2,6,4,5,3,7,1" | ||||||||||||||||||||||||||||||||||||||||||
| 521 | say join ",", $foo->array; | ||||||||||||||||||||||||||||||||||||||||||
| 522 | # 2,6,4,5,3,7,1 | ||||||||||||||||||||||||||||||||||||||||||
| 523 | |||||||||||||||||||||||||||||||||||||||||||
| 524 | my $bar = Math::Permutation->unrank(5, 19); | ||||||||||||||||||||||||||||||||||||||||||
| 525 | say $bar->sprint_cycles; | ||||||||||||||||||||||||||||||||||||||||||
| 526 | # (2 5 4 3) | ||||||||||||||||||||||||||||||||||||||||||
| 527 | # Note that there is no canonical cycle representation in this module, | ||||||||||||||||||||||||||||||||||||||||||
| 528 | # so each time the output may be slightly different. | ||||||||||||||||||||||||||||||||||||||||||
| 529 | |||||||||||||||||||||||||||||||||||||||||||
| 530 | my $goo = Math::Permutation->clone($foo); | ||||||||||||||||||||||||||||||||||||||||||
| 531 | say $goo->sprint_cycles; | ||||||||||||||||||||||||||||||||||||||||||
| 532 | # (1 2 6 7) (4 5 3) | ||||||||||||||||||||||||||||||||||||||||||
| 533 | |||||||||||||||||||||||||||||||||||||||||||
| 534 | $foo->inverse; | ||||||||||||||||||||||||||||||||||||||||||
| 535 | say $foo->sprint_cycles; | ||||||||||||||||||||||||||||||||||||||||||
| 536 | # (4 3 5) (1 7 6 2) | ||||||||||||||||||||||||||||||||||||||||||
| 537 | |||||||||||||||||||||||||||||||||||||||||||
| 538 | $foo->comp($goo); | ||||||||||||||||||||||||||||||||||||||||||
| 539 | say $foo->sprint_cycles; | ||||||||||||||||||||||||||||||||||||||||||
| 540 | # () | ||||||||||||||||||||||||||||||||||||||||||
| 541 | |||||||||||||||||||||||||||||||||||||||||||
| 542 | say $bar->rank; # 19 | ||||||||||||||||||||||||||||||||||||||||||
| 543 | $bar->prev; | ||||||||||||||||||||||||||||||||||||||||||
| 544 | say $bar->rank; # 18 | ||||||||||||||||||||||||||||||||||||||||||
| 545 | say $goo->rank; # 1264 | ||||||||||||||||||||||||||||||||||||||||||
| 546 | $goo->nxt; | ||||||||||||||||||||||||||||||||||||||||||
| 547 | say $goo->rank; # 1265 | ||||||||||||||||||||||||||||||||||||||||||
| 548 | |||||||||||||||||||||||||||||||||||||||||||
| 549 | say $goo->is_even; # 0 | ||||||||||||||||||||||||||||||||||||||||||
| 550 | say $goo->sgn; # -1 | ||||||||||||||||||||||||||||||||||||||||||
| 551 | |||||||||||||||||||||||||||||||||||||||||||
| 552 | use Data::Dump qw/dump/; | ||||||||||||||||||||||||||||||||||||||||||
| 553 | say $bar->sprint_wrepr; | ||||||||||||||||||||||||||||||||||||||||||
| 554 | dump $bar->matrix; | ||||||||||||||||||||||||||||||||||||||||||
| 555 | |||||||||||||||||||||||||||||||||||||||||||
| 556 | # "1,4,5,3,2" | ||||||||||||||||||||||||||||||||||||||||||
| 557 | # [ | ||||||||||||||||||||||||||||||||||||||||||
| 558 | # [1, 0, 0, 0, 0], | ||||||||||||||||||||||||||||||||||||||||||
| 559 | # [0, 0, 0, 0, 1], | ||||||||||||||||||||||||||||||||||||||||||
| 560 | # [0, 0, 0, 1, 0], | ||||||||||||||||||||||||||||||||||||||||||
| 561 | # [0, 1, 0, 0, 0], | ||||||||||||||||||||||||||||||||||||||||||
| 562 | # [0, 0, 1, 0, 0], | ||||||||||||||||||||||||||||||||||||||||||
| 563 | # ] | ||||||||||||||||||||||||||||||||||||||||||
| 564 | |||||||||||||||||||||||||||||||||||||||||||
| 565 | |||||||||||||||||||||||||||||||||||||||||||
| 566 | |||||||||||||||||||||||||||||||||||||||||||
| 567 | |||||||||||||||||||||||||||||||||||||||||||
| 568 | =head1 METHODS | ||||||||||||||||||||||||||||||||||||||||||
| 569 | |||||||||||||||||||||||||||||||||||||||||||
| 570 | =head2 INITALIZE/GENERATE NEW PERMUTATION | ||||||||||||||||||||||||||||||||||||||||||
| 571 | |||||||||||||||||||||||||||||||||||||||||||
| 572 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 573 | |||||||||||||||||||||||||||||||||||||||||||
| 574 | =item $p->init($n) | ||||||||||||||||||||||||||||||||||||||||||
| 575 | |||||||||||||||||||||||||||||||||||||||||||
| 576 | Initialize $p with the identity permutation of $n elements. | ||||||||||||||||||||||||||||||||||||||||||
| 577 | |||||||||||||||||||||||||||||||||||||||||||
| 578 | =item $p->wrepr([$a, $b, $c, ..., $m]) | ||||||||||||||||||||||||||||||||||||||||||
| 579 | |||||||||||||||||||||||||||||||||||||||||||
| 580 | Initialize $p with word representation of a permutation, a.k.a. one-line form. | ||||||||||||||||||||||||||||||||||||||||||
| 581 | |||||||||||||||||||||||||||||||||||||||||||
| 582 | =item $p->tabular([$a, $b, ... , $m], [$pa, $pb, $pc, ..., $pm]) | ||||||||||||||||||||||||||||||||||||||||||
| 583 | |||||||||||||||||||||||||||||||||||||||||||
| 584 | Initialize $p with the rules of a permutation, with input of permutation on the first list, | ||||||||||||||||||||||||||||||||||||||||||
| 585 | the output of permutation. If the first list is [1..$n], it is often called two-line form, | ||||||||||||||||||||||||||||||||||||||||||
| 586 | and the second list would be the word representation. | ||||||||||||||||||||||||||||||||||||||||||
| 587 | |||||||||||||||||||||||||||||||||||||||||||
| 588 | =item $p->cycles([[$a, $b, $c], [$d, $e], [$f, $g]]) | ||||||||||||||||||||||||||||||||||||||||||
| 589 | |||||||||||||||||||||||||||||||||||||||||||
| 590 | =item $p->cycles_with_len($n, [[$a, $b, $c], [$d, $e], [$f, $g]]) | ||||||||||||||||||||||||||||||||||||||||||
| 591 | |||||||||||||||||||||||||||||||||||||||||||
| 592 | Initialize $p by the cycle notation. If the length is not specific, the length would be the largest element in the cycles. | ||||||||||||||||||||||||||||||||||||||||||
| 593 | |||||||||||||||||||||||||||||||||||||||||||
| 594 | =item $p->unrank($n, $i) | ||||||||||||||||||||||||||||||||||||||||||
| 595 | |||||||||||||||||||||||||||||||||||||||||||
| 596 | Initialize $p referring to the lexicological rank of all $n-permutations. $i must be between 1 and $n!. | ||||||||||||||||||||||||||||||||||||||||||
| 597 | |||||||||||||||||||||||||||||||||||||||||||
| 598 | Note: The current version is not optimal. It is using an O(n^2) implementation, instead of the best O(n log n) implementation. | ||||||||||||||||||||||||||||||||||||||||||
| 599 | |||||||||||||||||||||||||||||||||||||||||||
| 600 | =item $p->random($n) | ||||||||||||||||||||||||||||||||||||||||||
| 601 | |||||||||||||||||||||||||||||||||||||||||||
| 602 | Initialize $p by a randomly selected $n-permutation. | ||||||||||||||||||||||||||||||||||||||||||
| 603 | |||||||||||||||||||||||||||||||||||||||||||
| 604 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 605 | |||||||||||||||||||||||||||||||||||||||||||
| 606 | =head2 DISPLAY THE PERMUTATION | ||||||||||||||||||||||||||||||||||||||||||
| 607 | |||||||||||||||||||||||||||||||||||||||||||
| 608 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 609 | |||||||||||||||||||||||||||||||||||||||||||
| 610 | =item $p->array() | ||||||||||||||||||||||||||||||||||||||||||
| 611 | |||||||||||||||||||||||||||||||||||||||||||
| 612 | Return an array showing the permutation. | ||||||||||||||||||||||||||||||||||||||||||
| 613 | |||||||||||||||||||||||||||||||||||||||||||
| 614 | =item $p->sprint_wrepr() | ||||||||||||||||||||||||||||||||||||||||||
| 615 | |||||||||||||||||||||||||||||||||||||||||||
| 616 | Return a string displaying the word representation of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 617 | |||||||||||||||||||||||||||||||||||||||||||
| 618 | =item $p->sprint_tabular() | ||||||||||||||||||||||||||||||||||||||||||
| 619 | |||||||||||||||||||||||||||||||||||||||||||
| 620 | Return a two-line string displaying the tabular form of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 621 | |||||||||||||||||||||||||||||||||||||||||||
| 622 | =item $p->sprint_cycles() | ||||||||||||||||||||||||||||||||||||||||||
| 623 | |||||||||||||||||||||||||||||||||||||||||||
| 624 | Return a string with cycles of $p. One-cycles are omitted. | ||||||||||||||||||||||||||||||||||||||||||
| 625 | |||||||||||||||||||||||||||||||||||||||||||
| 626 | =item $p->sprint_cycles_full() | ||||||||||||||||||||||||||||||||||||||||||
| 627 | |||||||||||||||||||||||||||||||||||||||||||
| 628 | Return a string with cycles of $p. One-cycles are included. | ||||||||||||||||||||||||||||||||||||||||||
| 629 | |||||||||||||||||||||||||||||||||||||||||||
| 630 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 631 | |||||||||||||||||||||||||||||||||||||||||||
| 632 | =head2 CHECK EQUIVALENCE BETWEEN PERMUTATIONS | ||||||||||||||||||||||||||||||||||||||||||
| 633 | |||||||||||||||||||||||||||||||||||||||||||
| 634 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 635 | |||||||||||||||||||||||||||||||||||||||||||
| 636 | =item $p->eqv($q) | ||||||||||||||||||||||||||||||||||||||||||
| 637 | |||||||||||||||||||||||||||||||||||||||||||
| 638 | Check if the permutation $q is equivalent to $p. Return 1 if yes, 0 otherwise. | ||||||||||||||||||||||||||||||||||||||||||
| 639 | |||||||||||||||||||||||||||||||||||||||||||
| 640 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 641 | |||||||||||||||||||||||||||||||||||||||||||
| 642 | =head2 CLONE THE PERMUTATION | ||||||||||||||||||||||||||||||||||||||||||
| 643 | |||||||||||||||||||||||||||||||||||||||||||
| 644 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 645 | |||||||||||||||||||||||||||||||||||||||||||
| 646 | =item $p->clone($q) | ||||||||||||||||||||||||||||||||||||||||||
| 647 | |||||||||||||||||||||||||||||||||||||||||||
| 648 | Clone the permutation $q into $p. | ||||||||||||||||||||||||||||||||||||||||||
| 649 | |||||||||||||||||||||||||||||||||||||||||||
| 650 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 651 | |||||||||||||||||||||||||||||||||||||||||||
| 652 | =head2 MODIFY THE PERMUTATION | ||||||||||||||||||||||||||||||||||||||||||
| 653 | |||||||||||||||||||||||||||||||||||||||||||
| 654 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 655 | |||||||||||||||||||||||||||||||||||||||||||
| 656 | =item $p->swap($i, $j) | ||||||||||||||||||||||||||||||||||||||||||
| 657 | |||||||||||||||||||||||||||||||||||||||||||
| 658 | Swap the values of $i-th position and $j-th position. | ||||||||||||||||||||||||||||||||||||||||||
| 659 | |||||||||||||||||||||||||||||||||||||||||||
| 660 | =item $p->comp($q) | ||||||||||||||||||||||||||||||||||||||||||
| 661 | |||||||||||||||||||||||||||||||||||||||||||
| 662 | Composition of $p and $q, sometimes called multiplication of the permutations. | ||||||||||||||||||||||||||||||||||||||||||
| 663 | The resultant is $q $p (first do $p, then do $q). | ||||||||||||||||||||||||||||||||||||||||||
| 664 | |||||||||||||||||||||||||||||||||||||||||||
| 665 | $p and $q must be permutations of same number of elements. | ||||||||||||||||||||||||||||||||||||||||||
| 666 | |||||||||||||||||||||||||||||||||||||||||||
| 667 | =item $p->inverse() | ||||||||||||||||||||||||||||||||||||||||||
| 668 | |||||||||||||||||||||||||||||||||||||||||||
| 669 | Inverse of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 670 | |||||||||||||||||||||||||||||||||||||||||||
| 671 | =item $p->nxt() | ||||||||||||||||||||||||||||||||||||||||||
| 672 | |||||||||||||||||||||||||||||||||||||||||||
| 673 | The next permutation under the lexicological order of all $n-permutations. | ||||||||||||||||||||||||||||||||||||||||||
| 674 | |||||||||||||||||||||||||||||||||||||||||||
| 675 | Caveat: may return []. | ||||||||||||||||||||||||||||||||||||||||||
| 676 | |||||||||||||||||||||||||||||||||||||||||||
| 677 | =item $p->prev() | ||||||||||||||||||||||||||||||||||||||||||
| 678 | |||||||||||||||||||||||||||||||||||||||||||
| 679 | The previous permutation under the lexicological order of all $n-permutations. | ||||||||||||||||||||||||||||||||||||||||||
| 680 | |||||||||||||||||||||||||||||||||||||||||||
| 681 | Caveat: may return []. | ||||||||||||||||||||||||||||||||||||||||||
| 682 | |||||||||||||||||||||||||||||||||||||||||||
| 683 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 684 | |||||||||||||||||||||||||||||||||||||||||||
| 685 | =head2 PRORERTIES OF THE CURRENT PERMUTATION | ||||||||||||||||||||||||||||||||||||||||||
| 686 | |||||||||||||||||||||||||||||||||||||||||||
| 687 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 688 | |||||||||||||||||||||||||||||||||||||||||||
| 689 | =item $p->sigma($i) | ||||||||||||||||||||||||||||||||||||||||||
| 690 | |||||||||||||||||||||||||||||||||||||||||||
| 691 | Return what $i is mapped to under $p. | ||||||||||||||||||||||||||||||||||||||||||
| 692 | |||||||||||||||||||||||||||||||||||||||||||
| 693 | =item $p->rule() | ||||||||||||||||||||||||||||||||||||||||||
| 694 | |||||||||||||||||||||||||||||||||||||||||||
| 695 | Return the word representation of $p as a list. | ||||||||||||||||||||||||||||||||||||||||||
| 696 | |||||||||||||||||||||||||||||||||||||||||||
| 697 | =item $p->cyc() | ||||||||||||||||||||||||||||||||||||||||||
| 698 | |||||||||||||||||||||||||||||||||||||||||||
| 699 | Return the cycle representation of $p as a list of list(s). | ||||||||||||||||||||||||||||||||||||||||||
| 700 | |||||||||||||||||||||||||||||||||||||||||||
| 701 | =item $p->elems() | ||||||||||||||||||||||||||||||||||||||||||
| 702 | |||||||||||||||||||||||||||||||||||||||||||
| 703 | Return the length of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 704 | |||||||||||||||||||||||||||||||||||||||||||
| 705 | =item $p->rank() | ||||||||||||||||||||||||||||||||||||||||||
| 706 | |||||||||||||||||||||||||||||||||||||||||||
| 707 | Return the lexicological rank of $p. See $p->unrank($n, $i). | ||||||||||||||||||||||||||||||||||||||||||
| 708 | |||||||||||||||||||||||||||||||||||||||||||
| 709 | Note: The current version is not optimal. It is using an O(n^2) implementation, instead of the best O(n log n) implementation. | ||||||||||||||||||||||||||||||||||||||||||
| 710 | |||||||||||||||||||||||||||||||||||||||||||
| 711 | =item $p->index() | ||||||||||||||||||||||||||||||||||||||||||
| 712 | |||||||||||||||||||||||||||||||||||||||||||
| 713 | Return the permutation index of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 714 | |||||||||||||||||||||||||||||||||||||||||||
| 715 | =item $p->order() | ||||||||||||||||||||||||||||||||||||||||||
| 716 | |||||||||||||||||||||||||||||||||||||||||||
| 717 | Return the order of $p, i.e. how many times the permutation acts on itself | ||||||||||||||||||||||||||||||||||||||||||
| 718 | and return the identity permutation. | ||||||||||||||||||||||||||||||||||||||||||
| 719 | |||||||||||||||||||||||||||||||||||||||||||
| 720 | =item $p->is_even() | ||||||||||||||||||||||||||||||||||||||||||
| 721 | |||||||||||||||||||||||||||||||||||||||||||
| 722 | Return whether $p is an even permutation. Return 1 or 0. | ||||||||||||||||||||||||||||||||||||||||||
| 723 | |||||||||||||||||||||||||||||||||||||||||||
| 724 | =item $p->is_odd() | ||||||||||||||||||||||||||||||||||||||||||
| 725 | |||||||||||||||||||||||||||||||||||||||||||
| 726 | Return whether $p is an odd permutation. Return 1 or 0. | ||||||||||||||||||||||||||||||||||||||||||
| 727 | |||||||||||||||||||||||||||||||||||||||||||
| 728 | =item $p->sgn() | ||||||||||||||||||||||||||||||||||||||||||
| 729 | |||||||||||||||||||||||||||||||||||||||||||
| 730 | Return the signature of $p. Return +1 if $p is even, -1 if $p is odd. | ||||||||||||||||||||||||||||||||||||||||||
| 731 | |||||||||||||||||||||||||||||||||||||||||||
| 732 | Another view is the determinant of the permutation matrix of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 733 | |||||||||||||||||||||||||||||||||||||||||||
| 734 | =item $p->inversion() | ||||||||||||||||||||||||||||||||||||||||||
| 735 | |||||||||||||||||||||||||||||||||||||||||||
| 736 | Return the inversion sequence of $p as a list. | ||||||||||||||||||||||||||||||||||||||||||
| 737 | |||||||||||||||||||||||||||||||||||||||||||
| 738 | =item $p->matrix() | ||||||||||||||||||||||||||||||||||||||||||
| 739 | |||||||||||||||||||||||||||||||||||||||||||
| 740 | Return the permutation matrix of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 741 | |||||||||||||||||||||||||||||||||||||||||||
| 742 | =item $p->fixed_points() | ||||||||||||||||||||||||||||||||||||||||||
| 743 | |||||||||||||||||||||||||||||||||||||||||||
| 744 | Return the list of fixed points of $p. | ||||||||||||||||||||||||||||||||||||||||||
| 745 | |||||||||||||||||||||||||||||||||||||||||||
| 746 | =item $p->sqrt() | ||||||||||||||||||||||||||||||||||||||||||
| 747 | |||||||||||||||||||||||||||||||||||||||||||
| 748 | Caveat: may return undef. | ||||||||||||||||||||||||||||||||||||||||||
| 749 | |||||||||||||||||||||||||||||||||||||||||||
| 750 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 751 | |||||||||||||||||||||||||||||||||||||||||||
| 752 | =head1 METHODS TO BE INPLEMENTED | ||||||||||||||||||||||||||||||||||||||||||
| 753 | |||||||||||||||||||||||||||||||||||||||||||
| 754 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 755 | |||||||||||||||||||||||||||||||||||||||||||
| 756 | =item longest_increasing() | ||||||||||||||||||||||||||||||||||||||||||
| 757 | |||||||||||||||||||||||||||||||||||||||||||
| 758 | =item longest_decreasing() | ||||||||||||||||||||||||||||||||||||||||||
| 759 | |||||||||||||||||||||||||||||||||||||||||||
| 760 | =item coxeter_decomposition() | ||||||||||||||||||||||||||||||||||||||||||
| 761 | |||||||||||||||||||||||||||||||||||||||||||
| 762 | =item comp( more than one permutations ) | ||||||||||||||||||||||||||||||||||||||||||
| 763 | |||||||||||||||||||||||||||||||||||||||||||
| 764 | =item reverse() | ||||||||||||||||||||||||||||||||||||||||||
| 765 | |||||||||||||||||||||||||||||||||||||||||||
| 766 | ref: Chapter 1, Patterns in Permutations and Words | ||||||||||||||||||||||||||||||||||||||||||
| 767 | |||||||||||||||||||||||||||||||||||||||||||
| 768 | =item complement() | ||||||||||||||||||||||||||||||||||||||||||
| 769 | |||||||||||||||||||||||||||||||||||||||||||
| 770 | ref: Chapter 1, Patterns in Permutations and Words | ||||||||||||||||||||||||||||||||||||||||||
| 771 | |||||||||||||||||||||||||||||||||||||||||||
| 772 | =item is_irreducible() | ||||||||||||||||||||||||||||||||||||||||||
| 773 | |||||||||||||||||||||||||||||||||||||||||||
| 774 | ref: Chapter 1, Patterns in Permutations and Words | ||||||||||||||||||||||||||||||||||||||||||
| 775 | |||||||||||||||||||||||||||||||||||||||||||
| 776 | =item num_of_occurrences_of_pattern() | ||||||||||||||||||||||||||||||||||||||||||
| 777 | |||||||||||||||||||||||||||||||||||||||||||
| 778 | ref: Chapter 1, Patterns in Permutations and Words | ||||||||||||||||||||||||||||||||||||||||||
| 779 | |||||||||||||||||||||||||||||||||||||||||||
| 780 | =item contains_pattern() | ||||||||||||||||||||||||||||||||||||||||||
| 781 | |||||||||||||||||||||||||||||||||||||||||||
| 782 | ref: Chapter 1, Patterns in Permutations and Words | ||||||||||||||||||||||||||||||||||||||||||
| 783 | |||||||||||||||||||||||||||||||||||||||||||
| 784 | =item avoids_pattern() | ||||||||||||||||||||||||||||||||||||||||||
| 785 | |||||||||||||||||||||||||||||||||||||||||||
| 786 | ref: Chapter 1, Patterns in Permutations and Words | ||||||||||||||||||||||||||||||||||||||||||
| 787 | |||||||||||||||||||||||||||||||||||||||||||
| 788 | including barred patterns | ||||||||||||||||||||||||||||||||||||||||||
| 789 | |||||||||||||||||||||||||||||||||||||||||||
| 790 | ref: Section 1.2, Patterns in Permutations and Words | ||||||||||||||||||||||||||||||||||||||||||
| 791 | |||||||||||||||||||||||||||||||||||||||||||
| 792 | Example: [ -3, -1, 5, -2, 4 ] | ||||||||||||||||||||||||||||||||||||||||||
| 793 | |||||||||||||||||||||||||||||||||||||||||||
| 794 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 795 | |||||||||||||||||||||||||||||||||||||||||||
| 796 | =head1 AUTHOR | ||||||||||||||||||||||||||||||||||||||||||
| 797 | |||||||||||||||||||||||||||||||||||||||||||
| 798 | Cheok-Yin Fung, C<< <fungcheokyin at gmail.com> >> | ||||||||||||||||||||||||||||||||||||||||||
| 799 | |||||||||||||||||||||||||||||||||||||||||||
| 800 | =head1 BUGS | ||||||||||||||||||||||||||||||||||||||||||
| 801 | |||||||||||||||||||||||||||||||||||||||||||
| 802 | Please report any bugs or feature requests to L<https://github.com/E7-87-83/Math-Permutation/issues>. | ||||||||||||||||||||||||||||||||||||||||||
| 803 | |||||||||||||||||||||||||||||||||||||||||||
| 804 | =head1 SUPPORT | ||||||||||||||||||||||||||||||||||||||||||
| 805 | |||||||||||||||||||||||||||||||||||||||||||
| 806 | You can find documentation for this module with the perldoc command. | ||||||||||||||||||||||||||||||||||||||||||
| 807 | |||||||||||||||||||||||||||||||||||||||||||
| 808 | perldoc Math::Permutation | ||||||||||||||||||||||||||||||||||||||||||
| 809 | |||||||||||||||||||||||||||||||||||||||||||
| 810 | |||||||||||||||||||||||||||||||||||||||||||
| 811 | You can also look for information at: | ||||||||||||||||||||||||||||||||||||||||||
| 812 | |||||||||||||||||||||||||||||||||||||||||||
| 813 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 814 | |||||||||||||||||||||||||||||||||||||||||||
| 815 | =item * RT: CPAN's request tracker (report bugs here) | ||||||||||||||||||||||||||||||||||||||||||
| 816 | |||||||||||||||||||||||||||||||||||||||||||
| 817 | L<https://rt.cpan.org/NoAuth/Bugs.html?Dist=Math-Permutation> | ||||||||||||||||||||||||||||||||||||||||||
| 818 | |||||||||||||||||||||||||||||||||||||||||||
| 819 | =item * Search CPAN | ||||||||||||||||||||||||||||||||||||||||||
| 820 | |||||||||||||||||||||||||||||||||||||||||||
| 821 | L<https://metacpan.org/release/Math-Permutation> | ||||||||||||||||||||||||||||||||||||||||||
| 822 | |||||||||||||||||||||||||||||||||||||||||||
| 823 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 824 | |||||||||||||||||||||||||||||||||||||||||||
| 825 | |||||||||||||||||||||||||||||||||||||||||||
| 826 | =head1 REFERENCES | ||||||||||||||||||||||||||||||||||||||||||
| 827 | |||||||||||||||||||||||||||||||||||||||||||
| 828 | The module has gained ideas from various sources: | ||||||||||||||||||||||||||||||||||||||||||
| 829 | |||||||||||||||||||||||||||||||||||||||||||
| 830 | Opensource resources: | ||||||||||||||||||||||||||||||||||||||||||
| 831 | |||||||||||||||||||||||||||||||||||||||||||
| 832 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 833 | |||||||||||||||||||||||||||||||||||||||||||
| 834 | =item * L<Julia Package Permutations.jl|https://github.com/scheinerman/Permutations.jl/blob/master/docs/src/index.md> | ||||||||||||||||||||||||||||||||||||||||||
| 835 | |||||||||||||||||||||||||||||||||||||||||||
| 836 | =item * L<CPAN Module Math::GSL::Permutation|https://metacpan.org/pod/Math::GSL::Permutation> | ||||||||||||||||||||||||||||||||||||||||||
| 837 | |||||||||||||||||||||||||||||||||||||||||||
| 838 | =item * L<Combinatorics features of Maxima|https://maxima.sourceforge.io/docs/manual/maxima_singlepage.html#combinatorics_002dpkg> | ||||||||||||||||||||||||||||||||||||||||||
| 839 | |||||||||||||||||||||||||||||||||||||||||||
| 840 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 841 | |||||||||||||||||||||||||||||||||||||||||||
| 842 | General resources: | ||||||||||||||||||||||||||||||||||||||||||
| 843 | |||||||||||||||||||||||||||||||||||||||||||
| 844 | =over 4 | ||||||||||||||||||||||||||||||||||||||||||
| 845 | |||||||||||||||||||||||||||||||||||||||||||
| 846 | =item * L<Wolfram Alpha|https://www.wolframalpha.com/> | ||||||||||||||||||||||||||||||||||||||||||
| 847 | |||||||||||||||||||||||||||||||||||||||||||
| 848 | =item * I<Algebra>, Michael Artin | ||||||||||||||||||||||||||||||||||||||||||
| 849 | |||||||||||||||||||||||||||||||||||||||||||
| 850 | =item * I<Patterns in Permutations and Words>, Sergey Kitaev | ||||||||||||||||||||||||||||||||||||||||||
| 851 | |||||||||||||||||||||||||||||||||||||||||||
| 852 | =back | ||||||||||||||||||||||||||||||||||||||||||
| 853 | |||||||||||||||||||||||||||||||||||||||||||
| 854 | =head1 LICENSE AND COPYRIGHT | ||||||||||||||||||||||||||||||||||||||||||
| 855 | |||||||||||||||||||||||||||||||||||||||||||
| 856 | This software is Copyright (c) 2022-2025 by Cheok-Yin Fung. | ||||||||||||||||||||||||||||||||||||||||||
| 857 | |||||||||||||||||||||||||||||||||||||||||||
| 858 | This is free software, licensed under: | ||||||||||||||||||||||||||||||||||||||||||
| 859 | |||||||||||||||||||||||||||||||||||||||||||
| 860 | MIT License | ||||||||||||||||||||||||||||||||||||||||||
| 861 | |||||||||||||||||||||||||||||||||||||||||||
| 862 | =cut | ||||||||||||||||||||||||||||||||||||||||||
| 863 | |||||||||||||||||||||||||||||||||||||||||||
| 864 | 8 | 1; # End of Math::Permutation | |||||||||||||||||||||||||||||||||||||||||