NumSeq/Xenodromes.pm

filter: Statementstmt 95.4% 104 / 109 Branchbran 90.9% 20 / 22 Conditioncond 66.6% 2 / 3 MC/DCmcdc 50.0% 1 / 2 Subroutinesub 94.1% 16 / 17 Podpod 100% 6 / 6 totaltotal 93.7% 149 / 159 CC 16 SCAR 12.8
CC
16
Cov
94%
next
6.0
ith
6.0
pred
5.0
CRAP 3.6
« NumSeq/OEIS/Catalogue.pm ↑ Summary NumSeq/OEIS/Catalogue/Plugin.pm »
1 # Copyright 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde
2  
3 # This file is part of Math-NumSeq.
4 #
5 # Math-NumSeq is free software; you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by the
7 # Free Software Foundation; either version 3, or (at your option) any later
8 # version.
9 #
10 # Math-NumSeq is distributed in the hope that it will be useful, but
11 # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 # for more details.
14 #
15 # You should have received a copy of the GNU General Public License along
16 # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
17  
18 package Math::NumSeq::Xenodromes;
19 1 ▶use 5.004;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 1 ▶use vars '$VERSION', '@ISA';
Subroutine BEGIN: called CC=1 SCAR=0.0
23 1 $VERSION = 75;
24  
25 1 ▶use Math::NumSeq;
Subroutine BEGIN: called CC=1 SCAR=0.0
26 1 ▶use Math::NumSeq::Base::IteratePred;
Subroutine BEGIN: called CC=1 SCAR=0.0
27 1 @ISA = ('Math::NumSeq::Base::IteratePred',
28 'Math::NumSeq');
29 1 *_is_infinite = \&Math::NumSeq::_is_infinite;
30  
31 1 ▶use Math::NumSeq::Repdigits;
Subroutine BEGIN: called CC=1 SCAR=0.0
32 1 *_digit_split_lowtohigh = \&Math::NumSeq::Repdigits::_digit_split_lowtohigh;
33  
34 # uncomment this to run the ### lines
35 #use Smart::Comments;
36  
37  
38 # use constant name => Math::NumSeq::__('...');
39 1 ▶use constant description => Math::NumSeq::__('Numbers with all digits distinct.');
Subroutine BEGIN: called CC=1 SCAR=0.0
40  
41 # This is i_start=1 value=0 following the OEIS and Palindromes.pm.
42 1 ▶use constant default_i_start => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
43 1 ▶use constant values_min => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
44  
45 use Math::NumSeq::Base::Digits
46 1 ▶ 'parameter_info_array'; # radix parameter
Subroutine BEGIN: called CC=1 SCAR=0.0
47  
48 0 ▶sub values_max {
Subroutine values_max: not called CC=1 SCAR=6.9
Pod documented
49 0 my ($self) = @_;
50 0 my $radix = $self->{'radix'};
51 0 return _digit_join_lowtohigh([reverse 0 .. $radix-1],
52 $radix);
53 }
54  
55 #------------------------------------------------------------------------------
56 # cf A036918 total count of xenodromes in base n
57 # A073531 count xenodromes with n digits
58 # A109303 non-xenodromes in decimal, at least one duplicate digit
59 # A178788 0/1 characteristic decimal distinct digits
60 # A029743 primes with distinct digits
61 # A001339 count xenodromes of n digits
62 # Sum (k+1)! * C(n,k), k = 0..n.
63 # = Sum (k+1)! * n!/k!*(n-k)!, k = 0..n.
64 # = Sum (k+1) * n!/(n-k)!, k = 0..n.
65 # = Sum k = 0..n of (k+1)*n*(n-1)*...*(n-k+1)
66 # A043537 how many distinct digits
67  
68 # OFFSET=1 for value=0
69 1 my @oeis_anum = (
70 # OEIS-Catalogue array begin
71 undef, # # 0
72 undef, # # 1
73 undef, # # radix=2 no seq with 0,1,2 only
74 'A023798', # radix=3
75 'A023799', # radix=4
76 'A023800', # radix=5
77 'A023801', # radix=6
78 'A023802', # radix=7
79 'A023803', # radix=8
80 'A023804', # radix=9
81 'A010784', #
82 'A023805', # radix=11
83 'A023806', # radix=12
84 'A023807', # radix=13
85 'A023808', # radix=14
86 'A023809', # radix=15
87 'A023810', # radix=16
88 # OEIS-Catalogue array end
89 );
90 1 ▶sub oeis_anum {
Subroutine oeis_anum: called CC=1 SCAR=0.0
Pod documented
91 1 my ($self) = @_;
92 1 return $oeis_anum[$self->{'radix'}];
93 }
94  
95 #------------------------------------------------------------------------------
96  
97 3 ▶sub rewind {
Subroutine rewind: called CC=1 SCAR=0.0
Pod documented
98 3 my ($self) = @_;
99 3 $self->{'i'} = $self->i_start;
100 3 $self->{'digits'} = [ -1 ];
101 3 $self->{'skip'} = [ '' ];
102 }
103 46 ▶sub next {
Subroutine next: called CC=6 SCAR=17.9
Pod documented
104 46 my ($self) = @_;
105  
106 46 my $radix = $self->{'radix'};
107 46 my $digits = $self->{'digits'}; # arrayref of integers
108 46 my $skip = $self->{'skip'}; # arrayref of strings
109  
110 ### Xenodromes next() ...
111 ### $digits
112  
113 46 my $pos = 0;
114 46 for (;;) {
115 ### at: "pos=$pos digits=".join(',',@$digits)
116  
117 58 my $digit = ++$digits->[$pos];
118 58 ▶ if (vec($skip->[$pos],$digit,1)) {
Branch: 1 branch
BranchTrueFalseTotal
if (vec $skip->[$pos], $digit, 1) 4 54 58
119 4 next;
120 }
121  
122 54 ▶ if ($digit >= $radix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($digit >= $radix) { } 4 50 54
123 ### ascend ...
124 4 $pos++;
125 4 ▶ if ($pos > $radix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pos > $radix) 0 4 4
126 0 return;
127 }
128 4 ▶ if ($pos > $#$digits) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pos > $digits->$#*) 2 2 4
129 ### extend to pos: $pos
130 2 $skip->[$pos] = '';
131 2 $digits->[$pos] = 0;
132 }
133 } else {
134 ### use digit: $digit
135 50 $digits->[$pos] = $digit;
136 50 ▶ if (--$pos < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (--$pos < 0) 46 4 50
137 46 return ($self->{'i'}++, _digit_join_lowtohigh($digits,$radix));
138 }
139 ### descend to pos: $pos
140 4 $digits->[$pos] = -1;
141 4 $skip->[$pos] = $skip->[$pos+1];
142 4 vec($skip->[$pos],$digit,1) = 1;
143 }
144 }
145 }
146  
147 # grand total
148 # 9 + 9*9 + 9*9*8 + 9*9*8*7 + ... + 9*9*8*7*6*5*4*3*2*1
149 # = 9*(1 + 9 + 9*8 + 9*8*7 + ... + 9*8*7*6*5*4*3*2*1)
150 # = 9*(1 + 9*(1 + 8 + 8*7 + ... + 8*7*6*5*4*3*2*1))
151 # = 9*(1 + 9*(1 + 8*(1 + 7 + ... + 7*6*5*4*3*2*1)))
152 # = 9*(1 + 9*(1 + 8*(1 + 7*(1 + ... + 2*(1 + 1)))))
153  
154 # radix=6
155 # 1 2 3 4 5 6
156 # 5 + 5*5 + 5*5*4 + 5*5*4*3 + 5*5*4*3*2 + 5*5*4*3*2*1 = 1630
157 # 5*(1 + 5 + 5*4 + 5*4*3 + 5*4*3*2 + 5*4*3*2*1) = 1630
158 # 5*(1 + 5*(1 + 4 + 4*3 + 4*3*2 + 4*3*2*1)) = 1630
159 # 5*(1 + 5*(1 + 4*(1 + 3*(1 + 2*(1 + 1))))) = 1630
160 # 5*(1 + 5*(1 + 4*(1 + 3*(1 + 2*(1 + 1))))) = 1630
161 # 1 2 3 4 5 6
162  
163  
164 # 0 to 9 is 10 values
165 # 10 to 98 is 9*9=81
166 72 ▶sub ith {
Subroutine ith: called CC=6 SCAR=17.9
Pod documented
167 72 my ($self, $i) = @_;
168 ### Xenodromes ith(): $i
169  
170 72 my $radix = $self->{'radix'};
171 72 ▶ if ($i <= $radix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i <= $radix) 33 39 72
172 # i=1 to i=radix
173 33 return $i-1;
174 }
175  
176 39 $i -= $radix+1;
177 39 my $total = my $this = $radix-1;
178 39 my $len = 1;
179 39 for (;;) {
180 40 $total *= $this;
181 40 $this--;
182 40 $len++;
183 ### compare: "i=$i total=$total"
184 40 ▶ if ($i < $total) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < $total) 39 1 40
185 39 my @index;
186 39 foreach my $pos ($this+1 .. $radix-1) {
187 40 push @index, $i % $pos; # low to high
188 40 $i = int($i/$pos);
189 }
190 39 push @index, $i+1;
191 ### @index
192 ### assert: $i+1 < $radix
193  
194 39 my @xeno = (0 .. $radix-1);
195 39 my @digits;
196 39 ▶ while (@index) {
Branch: 1 branch
BranchTrueFalseTotal
if (@index) 79 39 118
197 79 my $i = pop @index;
198 79 push @digits, $xeno[$i]; # high to low
199 79 splice @xeno, $i, 1; # remove
200 }
201 39 @digits = reverse @digits; # now low to high
202 39 return _digit_join_lowtohigh(\@digits,$radix);
203 }
204 1 ▶ if ($len >= $radix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($len >= $radix) 0 1 1
205 0 return undef;
206 }
207 1 $i -= $total;
208 }
209 }
210  
211 72 ▶sub pred {
Subroutine pred: called CC=5 SCAR=16.1
Pod documented
212 72 my ($self, $value) = @_;
213 ### Xenodromes pred(): $value
214  
215 72 ▶ if ($value != int($value) || _is_infinite($value)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($value != int $value or _is_infinite($value)) 24 48 72
Condition66%2/3
$value != int $value or _is_infinite($value)
l!l&&r!l&&!r
24048
MC/DC50%1/2
$value != int $value or _is_infinite($value)
$value != int $value _is_infinite($value)
Truth table66%2/3
A or B
A= $value != int $valueB= _is_infinite($value)
ABresult
1X1
011
000
216 24 return 0;
217 }
218 48 $value = abs($value);
219  
220 48 my %seen;
221 48 foreach my $digit (_digit_split_lowtohigh($value, $self->{'radix'})) {
222 74 ▶ if ($seen{$digit}++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($seen{$digit}++) 2 72 74
223 2 return 0;
224 }
225 }
226 46 return 1;
227 }
228  
229 # $aref->[0] low digit
230 85 ▶sub _digit_join_lowtohigh {
Subroutine _digit_join_lowtohigh: called CC=2 SCAR=6.9
231 85 my ($aref, $radix) = @_;
232 85 my $n = 0;
233 85 foreach my $digit (reverse @$aref) { # high to low
234 151 $n *= $radix;
235 151 $n += $digit;
236 }
237 85 return $n;
238 }
239  
240 1 1;
241 __END__
« NumSeq/OEIS/Catalogue.pm ↑ Summary NumSeq/OEIS/Catalogue/Plugin.pm »