Re: Generic De Bruijn Sequence

Here's a version I wrote for (OT) A different kind of 'combinatorics'. It'll theoretically handle up to a 63 bit DeBruijn sequence, but that would require 8 Etabytes of ram, so is untested :) It has been tested on 31-bit sequence, which require 2GB of ram and completes in under 30 minutes:

#! perl -slw
use strict;
use bytes;
use Data::Dump qw[ pp ]; $Data::Dump::WIDTH = 1000;

### 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 $mask2 = ( 1<<( 2**$N+$N-1 ) )-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;

__END__
[download]

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.

In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit

Comment on Re: Generic De Bruijn Sequence Download Code

Replies are listed 'Best First'.
Re^2: Generic De Bruijn Sequence by QM (Parson) on Apr 19, 2017 at 18:09 UTC
I found a similar post in my search here earlier, but not that one. Probably some issue with whitespace and searching. -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]
Re^3: Generic De Bruijn Sequence by BrowserUk (Patriarch) on Apr 19, 2017 at 20:00 UTC
I'd forgotten I'd posted that CufP. (Are you interested in the C version if I can find it?)	[reply]
Re^4: Generic De Bruijn Sequence by QM (Parson) on Apr 19, 2017 at 22:52 UTC
Are you interested in the C version if I can find it? Not really, but thanks for asking. :D -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]


"be consistent"
	PerlMonks