[Numpy-discussion] De Bruijn sequence

Vincent Davis vincent at vincentdavis.net
Sat Feb 1 11:28:57 EST 2014


Sage sites "The algorithm used is from Frank Ruskey’s “Combinatorial
Generation”."
It looks like Frank Ruskey's orginal publication on the algorithm was
Joe Sawada and Frank Ruskey, "An Efficient Algorithm for Generating
Necklaces with Fixed Density", SIAM Journal of Computing 29:671-684, 1999.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.5237&rep=rep1&type=pdf

If you take a look at this page
http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html

You can get a C or Pascal program, the License in the attached program is.

/****************************************************************************
* C program to generate necklaces, Lyndon words, and De Bruijn
 *
* sequences.  The algorithm is CAT and is described in the book
*
* "Combinatorial Generation."  This program, was obtained from the
 *
* (Combinatorial) Object Server, COS, at http://www.theory.csc.uvic.ca/
*
* The inputs are n, the length of the string, k, the arity of the
*
* string, and density, the maximum number of non-0's in the string.
*
* The De Bruijn option doesn't make sense unless density >= n.
 *
* The program can be modified, translated to other languages, etc.,
*
* so long as proper acknowledgement is given (author and source).
*
* Programmer: Frank Ruskey (1994), translated to C by Joe Sawada
 *
*****************************************************************************/



Vincent Davis
720-301-3003


On Sat, Feb 1, 2014 at 8:57 AM, Peter Cock <p.j.a.cock at googlemail.com>
wrote:
>
> On Sat, Feb 1, 2014 at 3:40 PM, Ralf Gommers <ralf.gommers at gmail.com>
wrote:
> >
> > On Fri, Jan 24, 2014 at 12:26 AM, Vincent Davis <
vincent at vincentdavis.net>
> > wrote:
> >>
> >> I happen to be working with De Bruijn sequences. Is there any interest
in
> >> this being part of numpy/scipy?
> >>
> >> https://gist.github.com/vincentdavis/8588879
> >
> > That looks like an old copy of GPL code from Sage:
> >
http://git.sagemath.org/sage.git/tree/src/sage/combinat/debruijn_sequence.pyx
> >
> > Besides the licensing issue, it doesn't really belong in scipy and
certainly
> > not in numpy imho.
> >
> > Ralf
>
> If it is GPL code that would be a problem, but in terms of scope it might
> fit under Biopython given how much De Bruijn graphs are used in
> current sequence analysis.
>
> Regards,
>
> Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20140201/8a030d74/attachment.html>


More information about the NumPy-Discussion mailing list