NAME

Math::Sequence::DeBruijn - Abstract

SYNOPSIS

use Math::Sequence::DeBruijn;      # Exports 'debruijn'
use Math::Sequence::DeBruijn ();   # No exports.

DESCRIPTION

This module provides a single subroutine, debruijn, which returns a De Bruijn sequence for the given alphabet A and size n. A De Bruijn sequence of an alphabet A and size n is a cyclic sequence where every substring of length n over the alphabet A appears exactly once in the sequence.

For instance, if A = {0, 1} and n = 3, a possible De Bruijn sequence would be 00010111, as each possible substring of length 3 (000, 001, 010, 011, 100, 101, 110, and 111) appears exactly once. Note that the sequence is cyclic, so 110 can be found by looking at the last two, and first character of the sequence.

debruijn takes two arguments:

$alphabet

Either an arrayref with the symbols to be used in the alphabet, or a string witht the same. For binary strings, one would use [0, 1] or "01".

$n

The length of the substrings to consider.

The sequence is returned as a string.

Be aware that the sequence returned has length k^n, where k is the size of the alphabet. This is the optimal length, so it cannot be improved, but it does mean both the running time, and memory usage of the subroutine is exponential in its second argument.

EXAMPLE

debruijn ("Perl", 3);

This returns PPPePPrPPlPeePerPelPrePrrPrlPlePlrPlleeereelerrerlelrellrrrlrlll.

ACKNOWLEDGEMENT

The code is a port of the Python code given in the Wikipedia article about De Bruijn sequences.

DEVELOPMENT

The current sources of this module are found on github, git://github.com/Abigail/Math-Sequence-DeBruijn.git.

AUTHOR

Abigail, mailto:cpan@abigail.freedom.nl.

COPYRIGHT and LICENSE

Copyright (C) 2022 by Abigail.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

INSTALLATION

To install this module, run, after unpacking the tar-ball, the following commands:

perl Makefile.PL
make
make test
make install