<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>