more useful options | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
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.
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 :)
Note: both the above versions produce the 2N+N-1 bit complete sequence, rather than the 2N 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. 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".
I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
In reply to Binary DeBruijn sequences. by BrowserUk
|
|