Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re^2: Generic De Bruijn Sequence

by QM (Parson)
on Apr 19, 2017 at 23:07 UTC ( #1188339=note: print w/replies, xml ) Need Help??


in reply to Re: Generic De Bruijn Sequence
in thread Generic De Bruijn Sequence

De Bruijn is supposed to be cyclic AAACCCBCCACBBCBACABCAABBBABAA

Yes. The last $n-1 chars overlap with the beginning. The debug prints show each permutation lined up with the output string, so you can see how the graph is traversed and the output constructed. I could have just used the last char of each permutation, and had a true De Bruijn output, but that didn't suit my needs.

I found the Python code, but didn't like it because of the lack of explanation. To understand it, I have to trace code that does a lot of index math, instead of reading comments hinting at an algorithm that makes sense on a higher level. It's not far removed from pointer math and assembler code, so it doesn't seem very Pythonic, as they like to say.

If nothing else, my code at least tries to say what it's doing. So the next guy can try to understand it, and not blindly accept it, nor need to walk through on paper to believe that it's correct.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Replies are listed 'Best First'.
Re^3: Generic De Bruijn Sequence (updated)
by LanX (Bishop) on Apr 19, 2017 at 23:16 UTC
    > . The last $n-1 chars overlap with the beginning
    > debruijn.pl 5 2 AAEEDECEBEADDCDBDACCBCABBA 123456789012345678901234567890

    I don't understand how $n=5 (Alphabet size according to your code) results in length 26 instead of 25.

    please explain°

    edit

    >  walk through on paper to believe that it's correct.

    Your user image shows Richard P. Feynman and you are questioning scientific reviews in mathematics? Ironic :)

    UPDATE

    ") did you mean $t-1 ?

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)
    Je suis Charlie!

      ") did you mean $t-1 ?
      Yes. In my original code, I used $n for both. But later realized I could split that into 2 parameters. I probably used $n here through that mistake.

      -QM
      --
      Quantum Mechanics: The dreams stuff is made of

Re^3: Generic De Bruijn Sequence
by LanX (Bishop) on Apr 19, 2017 at 23:47 UTC
    > so it doesn't seem very Pythonic, as they like to say.

    seems to be a port of the ruby version which is pretty straight forward ported for a Perl hacker

    http://gist.github.com/jonelf/3423148

    update

    Basically it's a inductive solution building complex sequences from more primitive ones starting with (1,1).

    I'm sure porting to Perl, using longer var names and dumping part solutions would explain the idea.

    update

    Though finding the original article would be better.

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)
    Je suis Charlie!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1188339]
help
Chatterbox?
erix wouldn't mind a nice old windmill to live in... Mueller/Miller/ Molenaar
LanX likes Swedish clogs

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (6)
As of 2017-12-15 16:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (439 votes). Check out past polls.

    Notices?