yamātārājabhānasalagam

I needed a binary (alphabet 0|1) DeBruijn sequence, and found a simple rule for producing one (see the comments).

I first coded it using strings of '0' and '1' characters and a hash to detect words already included.

Very quick to code, but using one byte per bit, and a hash, the size rapidly chewed through gobs of memory, long before I reached my target of 31-bit words.

#! perl -slw
use strict;

### Prefer Ones:
### Write n zeros.
### Then, always write a one unless it would cause the repetition of a
+n n-length string;
### In which case, write a zero.

our $N //= 4;

my $seq = '0' x $N;
my %seen = ( $seq => 1 );
for( $N .. 2**$N ) {
    $seq .= ( not exists $seen{ substr( $seq, -( $N-1 ) ) . '1' } ) ? 
+'1' : '0';
    ++$seen{ substr( $seq, -$N ) };
}

$seq .= substr $seq, 0, $N-1;

print length $seq; <STDIN>;

my $re = '(.)(?=(' . '.'x($N-1) . '))';
print $1 . $2 while $seq =~ m[$re]g;
[download]

So then I coded another version that used vec to produce the sequence directly into bits; and another bitvector to track the words seen.

This was much tricker to code -- despite the apparent simplicity of the code -- and goes much higher, using a mere faction of the memory, but unfortunately stops before my target because vec (as of the version of Perl I'm using) still treats its second argument as a signed, 32-bit integer despite that a) negative offsets make no sense; b) I'm using a 64-bit version of Perl :(

(If you try it with -N=7 or greater, I strongly recommend redirecting the output, or disabling it, because watching 100s or 1000s of 0s & 1s scroll up the screen is a very boring occupation :)

#! perl -slw
use strict;

### Prefer Ones:
### Write n zeros.
### Then, always write a one unless it would cause the repetition of a
+n n-length string;
### In which case, write a zero.

our $N //= 4;

my $t1 = "b${ \(2**$N+$N-1) }";
my $seen = '';
my $mask1 = ( 1<<$N )-1;
my $seq = pack 'Q*', (0) x 100;
my $val = 0;

for( $N .. 2**$N+$N-1 ) {                   ## if N=5; 5 .. 36; if N=6
+, 6 .. 64+6-1 = 69;
    $val = ( $val << 1 ) & $mask1;
    vec( $seen, $val | 1, 1 ) or do{ $val |= 1; vec( $seq, $_, 1 ) = 1
+; };
    vec( $seen, $val    , 1 ) = 1;
}
print unpack $t1, $seq;
[download]

Note: both the above versions produce the 2^N+N-1 bit complete sequence, rather than the 2^N sequence that is shown in the Wikipedia page which only become complete once you 'wrap them around'.

Ultimately, I ended up moving to C to achieve my target, which even more tricky (damn, I miss vec in C), but it eventually allowed me to produce the 1/4GB binary sequence I was after.