File Coverage

blib/lib/Math/Sequence/DeBruijn.pm

Criterion	Covered	Total	%
statement	20	20	100.0
branch			n/a
condition			n/a
subroutine	7	7	100.0
pod			n/a
total	27	27	100.0

package Math::Sequence::DeBruijn;

use 5.028;
use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';
use experimental 'lexical_subs';
use Exporter ();

our $VERSION = '2022021301';
our @EXPORT  = qw [debruijn];
our @ISA     = qw [Exporter];


#
# This a translation of the Python program given at the Wikipedia
# page on De Bruijn sequences.
# (https://en.wikipedia.org/wiki/De_Bruijn_sequence)
#

sub debruijn ($alphabet, $n) {
    $alphabet = [split // => $alphabet] unless ref $alphabet;
    my $size  = @$alphabet;
    my @a     = (0) x ($size * $n);

    my $sequence = [];

    my sub db ($t, $p) {
        if ($t > $n) {
            push @$sequence => @a [1 .. $p] if $n % $p == 0;
        }
        else {
            $a [$t] = $a [$t - $p];
            __SUB__ -> ($t + 1, $p);
            foreach my $j ($a [$t - $p] + 1 .. ($size - 1)) {
                $a [$t] = $j;
                __SUB__ -> ($t + 1, $t);
            }
        }
    };

    db (1, 1);

    join "" => @$alphabet [@$sequence];
}



1;

__END__