[sage-combinat-devel] Ticket #10530
Hello, Ticket 10530 is still open (http://trac.sagemath.org/sage_trac/ticket/ 10530). I would greatly appreciate it if someone could review; it should be almost if not completely ready, since it has been reviewed a few times already. Thanks in advance, Eviatar -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: De Bruijn Sequences
Thank you for the information, Sébastien! The circular problem is
interesting; maybe support for operations on circular words could be
added in the future.
"They point is that, for necklaces, Lyndon words, dyck words, and the
like, the main mathematical object is not a word, but a set of
words. And the main operations are to count them, to iterate through
them, etc. So everything revolves around the corresponding enumerated
sets of words: Necklaces([2,1,1]), DyckWords(n), ..."
That makes sense. A rigorous definition of De Bruijn sequences, I
feel, should include the set of all possible sequences.
"Either we clearly foresee that people will eventually be interested
in operations like counting or iterating through all DeBruijn
sequences for a given alphabet/n."
Yes, I think it should be left open for future implementation. The
problem is that there are a minimal amount of cases where these can be
computed in reasonable time. Nonetheless, it is something I may add in
the future (if no one else does). Thus I think not having it return a
word would be more appropriate.
Nicolas, I was a bit unclear on the naming you suggested in the
review. Could you please clarify it?
Cheers!
On Jan 1, 2:31 pm, Sébastien Labbé wrote:
> Hi,
>
> > De Bruijn sequences are finite words. It would seem logical to include
> > De Bruijn sequences as finite words, since they do fit the definition.
>
> Amongst the method of the class WordGenerator, most return infinite
> words but some return finite words (like PalindromicDefectWord,
> RandomWord and fibonacci_tile).
>
> So if it is a finite word, then it could be represented as a python
> list, tuple, str, a function {0,1,2...n} -> or a finite iterator.
>
> > What is the reason for not including necklaces and Lyndon Words there,
> > for example? Are they not also words?
>
> Right, good question. The reason is simply that necklaces and Lyndon
> Words were already in Sage when we started working on
> sage/combinat/words in 2007. The uniformization has never been
> completed. We could also mention dyck word and yamanouchi words as
> well. But I think LyndonWord inherits from FiniteWord_list so it is
> partially linked.
>
> To illustrate my vision, I am making sure that the DeBruijnSequence
> satisfies its definition in two ways : (1) with your patch applied and
> (2) how it could be.
>
> With the patch available at #10530 :
>
>
> sage: L = DeBruijnSequence(2,3).first()
> sage: L
> [0, 0, 0, 1, 0, 1, 1, 1]
> sage: w = Word(L)
> sage: w
> word: 00010111
> sage: map(w.number_of_factors, [0,1,2,3])
> [1, 2, 4, 6]
>
> We are missing two factors of length 3 because the sequence is
> circular. By considering a certain power, we get the missing factors :
>
> sage: ww = w ^ (5/4)
> sage: ww
> word: 0001011100
> sage: map(ww.number_of_factors, [0,1,2,3])
> [1, 2, 4, 8]
>
> how it could be :
> --
>
> sage: w = words.DeBruijnSequence(2,3).first() #maybe this one is
> not natural for the user to find it...
> sage: w = DeBruijnSequence(2,3).first() #maybe this is
> better, but in either case, the following could be...
> sage: w
> word: 00010111
> sage: type(w)
>
> sage: map(w.number_of_factors, [0,1,2,3])
> [1, 2, 4, 6]
>
> We are missing two factors of length 3 because the sequence is
> circular. By considering a certain power, we get the missing factors :
>
> sage: ww = w ^ (5/4)
> sage: ww
> word: 0001011100
> sage: map(ww.number_of_factors, [0,1,2,3])
> [1, 2, 4, 8]
>
> ---
>
> There is one final important thing to consider :
>
> sage: L = [0, 0, 0, 1, 0, 1, 1, 1]
> sage: %timeit Word(L)
> 625 loops, best of 3: 186 µs per loop
>
> This is could be improved, but today it is like that. So if one wants
> to claim that 32.1 µs is 300 times faster than matematica to create
> the first element of B(2,3), keeping the result as a list might be a
> good idea as well. It depends what one wants to do with it.
>
> Cheers and happy new year!
>
> Sébastien
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: De Bruijn Sequences
Hello, De Bruijn sequences are finite words. It would seem logical to include De Bruijn sequences as finite words, since they do fit the definition. What is the reason for not including necklaces and Lyndon Words there, for example? Are they not also words? Cheers. On Dec 30, 2:25 pm, Sébastien Labbé wrote: > Hi Eviatar and Nicolas, > > > Speaking of which, one question for the sage-word people: should De > > Bruijn sequences be output as Words? > > I believe so. Well, if we want to get things similar together. Many > infinite sequences have already been implemented. They are available > here (or in sage/combinat/words/word_generators.py) : > > sage: words.[TAB] > > Object returned are sequences (or infinite words over a given > alphabet). They are slice-able and many other methods for infinite > words have been implemented. Infinite words can be coded by an > iterator or a function N -> Alphabet. Examples are in the following > file : sage/combinat/words/word_generator.py. > > What do you think? > > Maybe we could rename "words" by "sequences" , "sequencesBank" or something. > > > Should the set of all De Bruijn > > sequences be a Language? > > Languages are being implemented in the sage-combinat branch by Vincent > and me. But we use the definition : "the set of factors of a word, > where factor means a finite sequence of consecutive letters". > > Cheers, > > Sébastien -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: De Bruijn Sequences
Thank you. I responded there with some clarifications. -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: De Bruijn Sequences
Thank you for all your help! This is now Trac #10530, http://trac.sagemath.org/sage_trac/ticket/10530 -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: De Bruijn Sequences
What is "an_element" supposed to do, exactly? Should it return the first item in a list, a random one, etc? Thank you. -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: De Bruijn Sequences
Thank you, Now that I think of it cardinality would be easy to implement; there is a formula for it. Would it be fine to have a cardinality method but only return one sequence? -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: De Bruijn Sequences
Merry Christmas! My function implements the construction of a sequence. For example: sage: DeBruijnSequence(2,3) [0, 0, 0, 1, 0, 1, 1, 1] Also this: sage: DeBruijnSequence(['foo','bar'],3) ['foo', 'foo', 'foo', 'bar', 'foo', 'bar', 'bar', 'bar'] However, there are multiple possible outputs. Since these sequences are cyclical, many are redundant. As well, the number of these sequences for given inputs can become very large. In all uses of De Bruijn sequences I've encountered, only one of the outputs is used. Most of the algorithms for generating De Bruijn sequences also just generate one. The problem is that, as a consequence of generating one output, many of the standard methods for combinatorial objects (such as .list()) will not be applicable here. Is this acceptable? Thank you. -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] De Bruijn Sequences
I wrote a function to generate De Bruijn sequences. Is it necessary that it be similar to the other combinatorial objects? The problem is that these usually generate all possible results for each function, but this would be impractical for De Bruijn sequences. At B(2,5), 2048 sequences are possible, which gives you an idea. Combinatorica does not do this, and I can't see where it would be useful either. -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
