blib/lib/Math/Permutation.pm

filter: Statementstmt 60.3% 201 / 333 Branchbran 51.2% 41 / 80 Conditioncond 35.2% 6 / 17 MC/DCmcdc 20.0% 2 / 10 Subroutinesub 62.0% 31 / 50 Podpod 100% 33 / 33 totaltotal 60.0% 314 / 523 CC 79 SCAR 29.1
CC
79
Cov
58%
sqrt
90.0
tabular
72.0
cycles
39.4
CRAP 18.4
↑ Summary
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
BranchTrueFalseTotal
if ($x != 0) 14 13 27
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
BranchTrueFalseTotal
if $n != $n2 0 16 16
36 16 my $check = 0;
37 16 for (0..$n-1) {
38 120 ▶ $check++ if $wrepr->[$_] == $wrepr2->[$_];
Branch: 1 branch
BranchTrueFalseTotal
if $wrepr->[$_] == $wrepr2->[$_] 120 0 120
39 }
40 16 ▶ return $check == $n ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$check == $n ? : 16 0 16
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]
l!l
640
MC/DC0%0/1
$_[1] || [1]
$_[1]
Truth table50%1/2
A
A= $_[1]
Aresult
11
00
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
BranchTrueFalseTotal
unless (&all(sub { defined $check{$_}; } , 1 .. $n)) 0 64 64
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
BranchTrueFalseTotal
unless (&all(sub { defined $check1{$_}; } , 1 .. $n) and $n == scalar @codomain and &all(sub { defined $check2{$_}; } , 1 .. $n)) 0 0 0
Condition0%0/6
&all(sub { defined $check1{$_}; } , 1 .. $n) and $n == scalar @codomain and &all(sub { defined $check2{$_}; } , 1 .. $n)
!ll&&!rl&&r
000
&all(sub { defined $check1{$_}; } , 1 .. $n) and $n == scalar @codomain
!ll&&!rl&&r
000
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)
ABCresult
0XX0
10X0
1100
1111
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
BranchTrueFalseTotal
if ($check) 0 0 0
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
BranchTrueFalseTotal
if ($_ != int $_ or $_ <= 0) 0 2 2
Condition33%1/3
$_ != int $_ or $_ <= 0
l!l&&r!l&&!r
002
MC/DC0%0/2
$_ != int $_ or $_ <= 0
$_ != int $_ $_ <= 0
Truth table33%1/3
A or B
A= $_ != int $_B= $_ <= 0
ABresult
1X1
011
000
124 0 $check = 0;
125 0 last;
126 }
127 }
128 2 for (@cycles) {
129 2 ▶ if ((scalar uniq @{$_}) != (scalar @{$_})) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar &uniq(@{$_;}) != scalar @{$_;}) 0 2 2
130 0 $check = 0;
131 0 last;
132 }
133 }
134 2 ▶ if (!$check) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($check) 0 2 2
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
BranchTrueFalseTotal
if ($check) 2 0 2
142 2 ▶ if ((scalar uniq @elements) == (scalar @elements)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar &uniq(@elements) == scalar @elements) { } 2 0 2
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
BranchTrueFalseTotal
$qp[$_] == 0 ? : 0 0 0
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
BranchTrueFalseTotal
if (scalar @{$c;} > 1) { } 14 10 24
elsif (scalar @{$c;} == 1) { } 10 0 10
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
BranchTrueFalseTotal
$hash{$_} == 0 ? : 13 82 95
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
BranchTrueFalseTotal
&any(sub { $n == $_; } , @elements) ? : 0 2 2
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
BranchTrueFalseTotal
if scalar @cycles == 0 0 0 0
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
BranchTrueFalseTotal
if scalar @q != $n 0 28 28
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
BranchTrueFalseTotal
if ($ind <= $#rw and $rw[$ind - 1] < $rw[$ind]) 6 8 14
Condition66%2/3
$ind <= $#rw and $rw[$ind - 1] < $rw[$ind]
!ll&&!rl&&r
086
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]
ABresult
0X0
100
111
264 6 $ind++;
265 }
266 8 ▶ return [] if $ind == scalar @w;
Branch: 1 branch
BranchTrueFalseTotal
if $ind == scalar @w 0 8 8
267 8 my @suffix = tail $ind, @w;
268 8 my $i = 1;
269 8 ▶ $i++ until $w[-$ind-1] < $suffix[-$i];
Branch: 1 branch
BranchTrueFalseTotal
$w[-$ind - 1] < $suffix[-$i] or do { ++$i } 8 5 13
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
BranchTrueFalseTotal
if ($ind <= $#rw and $rw[$ind - 1] > $rw[$ind]) 6 8 14
Condition66%2/3
$ind <= $#rw and $rw[$ind - 1] > $rw[$ind]
!ll&&!rl&&r
086
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]
ABresult
0X0
100
111
281 6 $ind++;
282 }
283 8 ▶ return [] if $ind == scalar @w;
Branch: 1 branch
BranchTrueFalseTotal
if $ind == scalar @w 0 8 8
284 8 my @suffix = tail $ind, @w;
285 8 my $i = 1;
286 8 ▶ $i++ until $w[-$ind-1] > $suffix[-$i];
Branch: 1 branch
BranchTrueFalseTotal
$w[-$ind - 1] > $suffix[-$i] or do { ++$i } 8 4 12
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
BranchTrueFalseTotal
if $i != $n - 1 0 0 0
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
BranchTrueFalseTotal
if (scalar %hash != 0) 102 24 126
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
BranchTrueFalseTotal
$c != $c1 and do { do { push @cycle, $c; my $pre_c = $c; $c = $hash{$c}; delete $hash{$pre_c} } } 82 102 184
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
BranchTrueFalseTotal
if $w[$j] > $w[$j + 1] 0 0 0
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
BranchTrueFalseTotal
$num_of_two_swaps % 2 == 0 ? : 3 5 8
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
BranchTrueFalseTotal
$_[0]->is_even ? : 3 5 8
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
BranchTrueFalseTotal
$_[0]->is_even ? : 0 0 0
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
BranchTrueFalseTotal
if ($w[$j] != $k) 144 96 240
423 144 ▶ $i++ if $w[$j] > $k;
Branch: 1 branch
BranchTrueFalseTotal
if $w[$j] > $k 72 72 144
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
BranchTrueFalseTotal
if $_[0]{"_wrepr"}[$_ - 1] == $_ 0 184 184
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
BranchTrueFalseTotal
if (scalar @{$cycles[$i]} % 2 == 1) { } 0 0 0
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
BranchTrueFalseTotal
if (scalar(values %even_cycle) % 2 == 0) { } 0 0 0
477 0 my @epairs = pairs sort {$a<=>$b} values %even_cycle;
478 0 for (@epairs) {
479 0 ▶ if ($_->[0] != $_->[1]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($_->[0] != $_->[1]) 0 0 0
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
BranchTrueFalseTotal
unless defined $even_cycle{$i} 0 0 0
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
BranchTrueFalseTotal
$even_cycle{$_} == $even_cycle{$i} and $_ != $i 0 0 0
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
↑ Summary