# ETOOBUSY đźš€ minimal blogging for the impatient

# PWC134 - Pandigital Numbers

**TL;DR**

Here we are with TASK #1 from The Weekly Challenge #134. Enjoy!

# The challenge

Write a script to generate first 5

`Pandigital Numbers`

in base 10.As per the wikipedia, it says:

A pandigital number is an integer that in a given base has among its significant digits each digit used in the base at least once.

# The questions

I know that itâ€™s mainly Perl and Raku and that it says
*numbers*, but is it allowed to manipulate strings instead? I hope soâ€¦

The task is indeed very limited, so another question is: are we expected to generalize upon this task? Of courseâ€¦ Iâ€™m assuming yes!

I have to admit that I had a hard time understanding the question only
from the quote above - I eventually realized that we were talking about
all possible digits allowed in the base (e.g. for base `10`

I was
thinking that the only digits *used* were `0`

and `1`

â€¦). Anyway the
wikipedia page cleared it all.

Last, Iâ€™m understanding â€śthe first fiveâ€¦â€ť as â€śthe lowest fiveâ€¦â€ť, right?!?

# The solution

As anticipated in the questions, I decided to both address a more general problem and to have a strings-based approach.

The generalization part isâ€¦ up to some limit:

- we can cope with a generic base, but only as an integer between
`1`

and`36`

(both included). - we will accept a generic number of items to be printed out, but only up to the limit that our lazyness allows us. More on this later!

One insight is that, for low number of desired items, the solution will be some permutation upon the absolute minimum value (which can be found in the wikipedia page). In particular, in base 10 we have that this is the minimum:

```
1023456789
```

which means that the lowest numbers will all start with `1`

and then
contain some permutation of the rest of the string, i.e. `023456789`

,
that is a permutation upon 9 digits. This will give us the lowest $9!$
elements, which is a fair amount of pandigital numbers and we will bail
out if more are requested. In our case, 5 elements is well within the
limit!

Then I thought about doing the least number of permutations possible. It turns out that to take 5 elements we only need to fiddle with the last 3 digits, because this will give us 6 different permutations (i.e. one more than needed). More generally, if we need $n$ items, we will have to fiddle with $m$ digits at the end, such that $m! \leq n$.

At this point, though, there is the issue of getting the *lowest* ones.
Using a generic permutation algoritm would mean generating all $m!$
elements, then sorting them, then taking the first $n$. Ugh.

To cope with this problem, we can adopt an algorithm that generates all
permutations over a set *in order*. Of course, this means that the items
to be permuted adhere to some definition of ordering, which is indeed
our case (also working when the digits end and we start using letters,
like in hexadecimal numbers).

It turns out that such an algorithm is readily available and described in section Generation in lexicographic order.

Now we have everything we needâ€¦ on with Raku:

```
#!/usr/bin/env raku
use v6;
sub next-permutation (@arrangement) {
my $i = @arrangement.end - 1;
--$i while $i >= 0 && @arrangement[$i] >= @arrangement[$i + 1];
return unless $i >= 0;
my $j = @arrangement.end;
--$j while @arrangement[$i] >= @arrangement[$j];
@arrangement[$i, $j] = @arrangement[$j, $i];
@arrangement[$i + 1 .. *] = @arrangement[$i + 1 .. *].reverse;
return @arrangement;
}
subset PosInt of Int:D where * > 0;
subset Base of PosInt where * <= 36;
sub pandigital-numbers (PosInt $n is copy, Base $b) {
my ($n-digits, $factorial) = 1, 1;
$factorial *= ++$n-digits while $factorial < $n;
die "I'm too lazy for more general algorithms"
if $n-digits >= $b - 1;
state $p36-min = '1023456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
my $fix = $p36-min.substr(0, $b - $n-digits);
my @moving = $p36-min.substr($b - $n-digits, $n-digits).comb(/./);
gather while $n > 0 {
take $fix ~ @moving.join('');
@moving = next-permutation(@moving) if --$n;
};
}
sub MAIN (PosInt $n = 5, Base $b = 10) {
.put for pandigital-numbers($n, $b);
}
```

Iâ€™m particularly happy about function `next-permutation`

because itâ€™s
totally *stateless* - we give it an input arrangement, it computes the
next lexicographic permutation and gives it back.

The check in `pandigital-numbers`

is to make sure that this simplified
algorithm works. For anything beyondâ€¦ people can extend this!

The Perl counterpart is very similar:

```
#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
sub next_permutation (@arrangement) {
my $i = $#arrangement - 1;
--$i while $i >= 0 && $arrangement[$i] >= $arrangement[$i + 1];
return unless $i >= 0;
my $end = my $j = $#arrangement;
--$j while $arrangement[$i] >= $arrangement[$j];
@arrangement[$i, $j] = @arrangement[$j, $i];
@arrangement[$i + 1 .. $end] = reverse @arrangement[$i + 1 .. $end];
return @arrangement;
}
sub pandigital_numbers ($n = 5, $b = 10) {
my ($n_digits, $factorial) = (1, 1);
$factorial *= ++$n_digits while $factorial < $n;
die "I'm too lazy for more general algorithms"
if $n_digits >= $b - 1;
state $p36_min = '1023456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
my $fix = substr $p36_min, 0, $b - $n_digits;
my @moving = split m{}mxs, substr $p36_min, $b - $n_digits, $n_digits;
map {
@moving = next_permutation(@moving) if $_;
join '', $fix, @moving;
} 0 .. $n - 1;
}
say for pandigital_numbers(@ARGV);
```

The `gather`

/`take`

can be easily (and elegantly) transformed into a
`map`

, which is good. Apart from this, itâ€™s really a faithful
translation.

I hope you enjoyed the ride and until next timeâ€¦ stay safe!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*