<div dir="ltr">Sage sites "The algorithm used is from Frank Ruskey’s “Combinatorial Generation”."<br>It looks like Frank Ruskey's orginal publication on the algorithm was<br>Joe Sawada and Frank Ruskey, "An Efficient Algorithm for Generating Necklaces with Fixed Density", SIAM Journal of Computing 29:671-684, 1999.<br>

<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.5237&rep=rep1&type=pdf">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.5237&rep=rep1&type=pdf</a><br><br>If you take a look at this page<br>

<a href="http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html">http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html</a><br><br>You can get a C or Pascal program, the License in the attached program is.<br>

<br>/****************************************************************************<br>* C program to generate necklaces, Lyndon words, and De Bruijn              *<br>* sequences.  The algorithm is CAT and is described in the book             *<br>

* "Combinatorial Generation."  This program, was obtained from the          *<br>* (Combinatorial) Object Server, COS, at <a href="http://www.theory.csc.uvic.ca/">http://www.theory.csc.uvic.ca/</a>     *<br>* The inputs are n, the length of the string, k, the arity of the           *<br>

* string, and density, the maximum number of non-0's in the string.         *<br>* The De Bruijn option doesn't make sense unless density >= n.              *<br>* The program can be modified, translated to other languages, etc.,         *<br>

* so long as proper acknowledgement is given (author and source).           *<br>* Programmer: Frank Ruskey (1994), translated to C by Joe Sawada            *<br>*****************************************************************************/<br>

<br><br><br>Vincent Davis<br>720-301-3003<br><br><br>On Sat, Feb 1, 2014 at 8:57 AM, Peter Cock <<a href="mailto:p.j.a.cock@googlemail.com">p.j.a.cock@googlemail.com</a>> wrote:<br>><br>> On Sat, Feb 1, 2014 at 3:40 PM, Ralf Gommers <<a href="mailto:ralf.gommers@gmail.com">ralf.gommers@gmail.com</a>> wrote:<br>

> ><br>> > On Fri, Jan 24, 2014 at 12:26 AM, Vincent Davis <<a href="mailto:vincent@vincentdavis.net">vincent@vincentdavis.net</a>><br>> > wrote:<br>> >><br>> >> I happen to be working with De Bruijn sequences. Is there any interest in<br>

> >> this being part of numpy/scipy?<br>> >><br>> >> <a href="https://gist.github.com/vincentdavis/8588879">https://gist.github.com/vincentdavis/8588879</a><br>> ><br>> > That looks like an old copy of GPL code from Sage:<br>

> > <a href="http://git.sagemath.org/sage.git/tree/src/sage/combinat/debruijn_sequence.pyx">http://git.sagemath.org/sage.git/tree/src/sage/combinat/debruijn_sequence.pyx</a><br>> ><br>> > Besides the licensing issue, it doesn't really belong in scipy and certainly<br>

> > not in numpy imho.<br>> ><br>> > Ralf<br>><br>> If it is GPL code that would be a problem, but in terms of scope it might<br>> fit under Biopython given how much De Bruijn graphs are used in<br>

> current sequence analysis.<br>><br>> Regards,<br>><br>> Peter</div>