The following is an example of a branch and bound approach.
NB: Just a hack as a proof of concept, without taking advantage of the optimization ideas I've already described.
Nevertheless it calculates:
====== Calculating base 12
*** Results 18
took: 0 sec
====== Calculating base 14
*** Results 136
took: 0 sec
====== Calculating base 16
*** Results 188
took: 1 sec
====== Calculating base 18
*** Results 7478
took: 5 sec
====== Calculating base 20
*** Results 41984
took: 49 sec
use strict;
use warnings;
use Data::Dump qw/pp dd/;
use feature 'say';
my $base= 16;
my $verbose = 0 ;
my @digits = 0 .. $base-1;
my %allowed;
@allowed{@digits} = (1)x@digits;
delete $allowed{0};
#pp \%allowed;
our $i;
our $carry;
our $level;
our @factor;
our @product;
our @result;
warn "====== Calculating base $base\n";
my $start =time;
for $i ( reverse 2 .. $base -1 ) {
delete $allowed{$i} ;
warn "=== \$i = $i\n" if $verbose;
$carry = 0;
$level=0;
branch();
$allowed{$i}=1;
}
say "*** Results ", scalar @result;
say "took: ", time-$start , " sec";
sub branch {
#say pp \%allowed unless $level;
local $level = $level+1;
for my $f ( sort keys %allowed ) {
my $p = $i *$f + $carry;
my $digit = $p % $base;
local $carry = int ($p / $base);
next if $digit == $f;
next unless $allowed{$digit};
unshift @factor,$f;
unshift @product,$digit
;
warn " " x $level,
"Level$level <$f>: $i * @factor = @product with <$carry $d
+igit> remain ", (sort keys %allowed) ,
"\n" if $verbose > 2;
delete $allowed{$f};
delete $allowed{$digit};
if (keys %allowed) {
branch()
} elsif (! $carry) {
warn "-" x $level, "RESULT Level$level: $i * @factor = @
+product with <$carry $digit> remain ", (sort keys %allowed) , "\n" i
+f $verbose >1;
push @result, [ $i, [@factor], [@product]];
}
$allowed{$f} = 1 ;
$allowed{$digit} = 1 ;
shift @factor;
shift @product;
}
}
Update: code reformat.