File Coverage

blib/lib/Math/NumSeq/Xenodromes.pm
Criterion Covered Total %
statement 98 103 95.1
branch 18 20 90.0
condition 2 3 66.6
subroutine 16 17 94.1
pod 6 6 100.0
total 140 149 93.9


line stmt bran cond sub pod time code
1             # Copyright 2012, 2013, 2014 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 .
17              
18             package Math::NumSeq::Xenodromes;
19 1     1   5181 use 5.004;
  1         3  
20 1     1   3 use strict;
  1         1  
  1         19  
21              
22 1     1   3 use vars '$VERSION', '@ISA';
  1         1  
  1         51  
23             $VERSION = 72;
24              
25 1     1   632 use Math::NumSeq;
  1         2  
  1         20  
26 1     1   582 use Math::NumSeq::Base::IteratePred;
  1         1  
  1         34  
27             @ISA = ('Math::NumSeq::Base::IteratePred',
28             'Math::NumSeq');
29             *_is_infinite = \&Math::NumSeq::_is_infinite;
30              
31 1     1   606 use Math::NumSeq::Repdigits;
  1         2  
  1         39  
32             *_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     1   4 use constant description => Math::NumSeq::__('Numbers with all digits distinct.');
  1         1  
  1         2  
40              
41             # This is i_start=1 value=0 following the OEIS and Palindromes.pm.
42 1     1   3 use constant default_i_start => 1;
  1         1  
  1         32  
43 1     1   3 use constant values_min => 0;
  1         1  
  1         33  
44              
45             use Math::NumSeq::Base::Digits
46 1     1   3 'parameter_info_array'; # radix parameter
  1         1  
  1         504  
47              
48             sub values_max {
49 0     0 1 0 my ($self) = @_;
50 0         0 my $radix = $self->{'radix'};
51 0         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             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             sub oeis_anum {
91 1     1 1 3 my ($self) = @_;
92 1         1 return $oeis_anum[$self->{'radix'}];
93             }
94              
95             #------------------------------------------------------------------------------
96              
97             sub rewind {
98 3     3 1 426 my ($self) = @_;
99 3         9 $self->{'i'} = $self->i_start;
100 3         5 $self->{'digits'} = [ -1 ];
101 3         8 $self->{'skip'} = [ '' ];
102             }
103             sub next {
104 46     46 1 525 my ($self) = @_;
105              
106 46         34 my $radix = $self->{'radix'};
107 46         23 my $digits = $self->{'digits'}; # arrayref of integers
108 46         30 my $skip = $self->{'skip'}; # arrayref of strings
109              
110             ### Xenodromes next() ...
111             ### $digits
112              
113 46         28 my $pos = 0;
114 46         21 for (;;) {
115             ### at: "pos=$pos digits=".join(',',@$digits)
116              
117 58         41 my $digit = ++$digits->[$pos];
118 58 100       69 if (vec($skip->[$pos],$digit,1)) {
119 4         3 next;
120             }
121              
122 54 100       46 if ($digit >= $radix) {
123             ### ascend ...
124 4         3 $pos++;
125 4 50       5 if ($pos > $radix) {
126 0         0 return;
127             }
128 4 100       7 if ($pos > $#$digits) {
129             ### extend to pos: $pos
130 2         3 $skip->[$pos] = '';
131 2         2 $digits->[$pos] = 0;
132             }
133             } else {
134             ### use digit: $digit
135 50         33 $digits->[$pos] = $digit;
136 50 100       54 if (--$pos < 0) {
137 46         45 return ($self->{'i'}++, _digit_join_lowtohigh($digits,$radix));
138             }
139             ### descend to pos: $pos
140 4         2 $digits->[$pos] = -1;
141 4         5 $skip->[$pos] = $skip->[$pos+1];
142 4         8 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             sub ith {
167 72     72 1 81 my ($self, $i) = @_;
168             ### Xenodromes ith(): $i
169              
170 72         51 my $radix = $self->{'radix'};
171 72 100       82 if ($i <= $radix) {
172             # i=1 to i=radix
173 33         36 return $i-1;
174             }
175              
176 39         28 $i -= $radix+1;
177 39         24 my $total = my $this = $radix-1;
178 39         24 my $len = 1;
179 39         18 for (;;) {
180 40         26 $total *= $this;
181 40         17 $this--;
182 40         26 $len++;
183             ### compare: "i=$i total=$total"
184 40 100       47 if ($i < $total) {
185 39         23 my @index;
186 39         39 foreach my $pos ($this+1 .. $radix-1) {
187 40         28 push @index, $i % $pos; # low to high
188 40         44 $i = int($i/$pos);
189             }
190 39         28 push @index, $i+1;
191             ### @index
192             ### assert: $i+1 < $radix
193              
194 39         54 my @xeno = (0 .. $radix-1);
195 39         27 my @digits;
196 39         42 while (@index) {
197 79         52 my $i = pop @index;
198 79         62 push @digits, $xeno[$i]; # high to low
199 79         93 splice @xeno, $i, 1; # remove
200             }
201 39         19 @digits = reverse @digits; # now low to high
202 39         48 return _digit_join_lowtohigh(\@digits,$radix);
203             }
204 1 50       3 if ($len >= $radix) {
205 0         0 return undef;
206             }
207 1         2 $i -= $total;
208             }
209             }
210              
211             sub pred {
212 72     72 1 239 my ($self, $value) = @_;
213             ### Xenodromes pred(): $value
214              
215 72 100 66     128 if ($value != int($value) || _is_infinite($value)) {
216 24         21 return 0;
217             }
218 48         42 $value = abs($value);
219              
220 48         17 my %seen;
221 48         77 foreach my $digit (_digit_split_lowtohigh($value, $self->{'radix'})) {
222 74 100       119 if ($seen{$digit}++) {
223 2         3 return 0;
224             }
225             }
226 46         54 return 1;
227             }
228              
229             # $aref->[0] low digit
230             sub _digit_join_lowtohigh {
231 85     85   61 my ($aref, $radix) = @_;
232 85         44 my $n = 0;
233 85         71 foreach my $digit (reverse @$aref) { # high to low
234 151         90 $n *= $radix;
235 151         101 $n += $digit;
236             }
237 85         128 return $n;
238             }
239              
240             1;
241             __END__