Re: [sage-combinat-devel] Re: De Bruijn Sequences
Just a question/remark : a DeBruijn sequence is just a Hamiltonian cycle in the Rauzy graph of the full language right ? (remark that for the DeBruijn graph the problem of finding Hamiltonian path is equivalent to the one of looking for Euler cycles at the next level!). It could be nice to have pointers from the DeBruijn graph... Ok. So the set of all factors of a word is a factorial language. The converse does not hold, right? Out of curiosity, is there a characterization of those factorial languages that come from a word? When I say maximal element, it is for the relation contains x as factor. * if the word is finite : there is a maximal element which is the word itself. * if the word is infinite : you adapt the preceding definition at all finite steps : for all n there exists a word w in L such that w contains all words of length n of L. In other words, each finite subset admit a maximal element in L. Now, would it make sense to have a Languages category? With FactorialLanguages as subcategory? What kind of operations would those provide on parents (the languages), elements (their words), and morphisms? It could be useful to have the category framework because for a word morphism the image of the language of w is not the the language of the image... Cheers, Vincent -- 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
Hi again! On Thu, Dec 30, 2010 at 05:25:26PM -0500, Sébastien Labbé wrote: 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. Thanks for the clarification! Since ``Language`` is a very common name, and the use case above is only one of the many usages, would it be possible to use a more specific name for the above, at least in the global namespace? I don't know the terminology, but possibly something like FactorLanguage? Or LanguageOfFiniteFactors? Sorry, I realized my answer was wrong the day after when I was country skiing. A language is simply a set of words. The set can be finite or not. Elements can be finite words or infinite words, why not!? So ``Language`` is still the good name for it. Dyck words forms a language and the set B(2,3) of certain DeBruijn Sequences is a language as well. So what I said above (about that the definition we use for language) was wrong. I confused with the notion of language we often use (a factorial language). So don't worry, when I write code I spend more time making sure everything is fine than when I write emails. The code should look like the following : class Language class FactorialLanguage(Language) class UnionOfLanguage(Language) etc. Note : a factorial language is a language L such that w in L and u factor of w implies that u in L. So one question we will have to answer is : Does Language should inherits from CombinatorialClass? 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.
Re: [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. Yes, good point! I am thinking about it. Moreover, I believe CircularWord would behave the same as a PeriodicInfiniteWord, so I am thinking of implementing both at the same time. Thus I think not having it return a word would be more appropriate. Note that DeBruijnSequences(10,3).an_element() could still return a word. This second design choice is yours. I think an_element shoud be consistent with the iterator (either both return words or both return lists or both return tuples). And I am ok with returning a python object like list or tuple. It is more versatile like that and a word can still be created from it. 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
Hi Sébastien! How was the skiing? Lucky you :-) On Mon, Jan 03, 2011 at 12:45:31PM -0500, Sébastien Labbé wrote: Sorry, I realized my answer was wrong the day after when I was country skiing. A language is simply a set of words. The set can be finite or not. Elements can be finite words or infinite words, why not!? So ``Language`` is still the good name for it. Dyck words forms a language and the set B(2,3) of certain DeBruijn Sequences is a language as well. Perfect, we are on the same line :-) So what I said above (about that the definition we use for language) was wrong. I confused with the notion of language we often use (a factorial language). So don't worry, when I write code I spend more time making sure everything is fine than when I write emails. :-) The code should look like the following : class Language class FactorialLanguage(Language) class UnionOfLanguage(Language) etc. Note : a factorial language is a language L such that w in L and u factor of w implies that u in L. Ok. So the set of all factors of a word is a factorial language. The converse does not hold, right? Out of curiosity, is there a characterization of those factorial languages that come from a word? So one question we will have to answer is : Does Language should inherits from CombinatorialClass? CombinatorialClass is deprecated :-) But yes, that's worth investigation! Here is some fuel. A language is a set of words. Therefore it would naturally be modelled by a Parent in Sage. That Parent would (at the very least) be in the Sets() category. Sometimes in EnumeratedSets(), but not always (not all languages can be enumerated). Now, would it make sense to have a Languages category? With FactorialLanguages as subcategory? What kind of operations would those provide on parents (the languages), elements (their words), and morphisms? Some typical parents in those categories would include: FactorialLanguage(word) UnionOfLanguages([A,B,C]) ... The category framework would, e.g., provide some automatic support for deciding that the union/intersection/... of two finite (resp factorial) languages is again finite (resp. factorial). Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
On Mon, Jan 03, 2011 at 12:53:42PM -0500, Sébastien Labbé wrote: Note that DeBruijnSequences(10,3).an_element() could still return a word. This second design choice is yours. I think an_element shoud be consistent with the iterator (either both return words or both return lists or both return tuples). Definitely. As well of course as all operations returning elements. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
On Sat, Jan 01, 2011 at 09:13:23PM -0800, Eviatar wrote: 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). Ok. Just a comment which does not neccessarily apply here: even huge enumerated sets (where full iteration would not be possible) can afford useful operations, like random generation. Thus I think not having it return a word would be more appropriate. Note that DeBruijnSequences(10,3).an_element() could still return a word. This second design choice is yours. Nicolas, I was a bit unclear on the naming you suggested in the review. Could you please clarify it? Done there! Ah, a last point. To choose between implementing: DeBruijnSequences(10,3).an_element() or DeBruijnSequences(10,3).first() You should consider whether the returned sequence will indeed be the first one, once iteration will be implemented. I.e. it is the smallest one for the natural iteration order (lexicographic?). In doubt, use an_element. Anyway, any non empty set should implement an_element. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
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)
class 'sage.combinat.words.word.FiniteWord_list'
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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
Hi!
On Sat, Jan 01, 2011 at 05:31:13PM -0500, Sébastien Labbé wrote:
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.
Thanks Sébastien for the feedback!
What is the reason for not including necklaces and Lyndon Words there,
for example? Are they not also words?
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), ...
Granted, there is still some merging and cleanup to do. For example,
the elements of DyckWords(n) could possibly be returned as words, etc.
Comming back to DeBruijn sequences, I see two options:
- 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. And then the entry point for the
user shall be:
sage: DeBruijnSequences(alphabet, n)
The set all de Bruijn sequences over ...
with a 's', even if for the moment an_element is the only
implemented feature:
sage: DeBruijnSequences(alphabet, n).an_element()
[ ]
- Or all we really care about is to construct one De Bruijn sequence
for that alphabet and n, and then it should be:
sage: words.DeBruijnSequence(alphabet,n)
[ ... ]
An independent question is to decide whether the result shall be a
tuple, a word, or ... It is perfectly fine to leave this not specified
to leave our hands free for the future; e.g. just say that the result
is an iterable l which also supports random access (i.e. l[i]), and
possibly len(l).
I let you choose whatever feels more appropriate!
Cheers,
Nicolas
--
Nicolas M. Thiéry Isil nthi...@users.sf.net
http://Nicolas.Thiery.name/
--
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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
Hi Sébastien, On Thu, Dec 30, 2010 at 05:25:26PM -0500, Sébastien Labbé wrote: 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. Thanks for the clarification! Since ``Language`` is a very common name, and the use case above is only one of the many usages, would it be possible to use a more specific name for the above, at least in the global namespace? I don't know the terminology, but possibly something like FactorLanguage? Or LanguageOfFiniteFactors? Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
Hi! This has nothing to do with deBruijn sequences, but since you are all discussing words: at the last Sage days some new methods for words were implemented that are useful for crystals, see http://trac.sagemath.org/sage_trac/ticket/10446 Are these in the right spot? Cheers, Anne -- 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 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é sla...@gmail.com 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)
class 'sage.combinat.words.word.FiniteWord_list'
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é sla...@gmail.com 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
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
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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
On Tue, Dec 28, 2010 at 12:06:52PM -0800, Eviatar wrote: What is an_element supposed to do, exactly? Should it return the first item in a list, a random one, etc? Does this help? sage: C = Sets().parent_class sage: C.an_element? ... Docstring: Returns a (preferably typical) element of this parent. This is used both for illustration and testing purposes. If the set ``self`` is empty, ``an_element()`` should raise the exception ``EmptySetError``. This default implementation calls ``_an_element_()`` and cache the result. Any parent should implement either ``an_element()`` or ``_an_element_()``. sage: C = EnumeratedSets().parent_class sage: C._an_element_? Type: CachedMethodCaller Base Class: class 'sage.misc.cachefunc.CachedMethodCaller' String Form:Cached version of function _an_element_from_iterator at 0x2a93de8 Namespace: Interactive File: /opt/sage/local/lib/python2.6/site-packages/sage/misc/cachefunc.py Definition: C._an_element_(self, *args, **kwds) Docstring: An element in ``self``. ``self.an_element()`` returns a particular element of the set ``self``. This is a generic implementation from the category ``EnumeratedSets()`` which can be used when the method ``__iter__`` is provided. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
Re: [sage-combinat-devel] Re: De Bruijn Sequences
On Sat, Dec 25, 2010 at 04:28:36PM -0800, Eviatar wrote: 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. Thanks for the clarification! I don't remember meeting this use case so far. I guess: sage: DeBruijnSequences(['foo','bar'],3).first() or sage: DeBruijnSequences(['foo','bar'],3).an_element() would do. Though I agree that this is a bit of an overkill if this is the only operation that is ever going to be implemented on de Bruijn sequences. So I could be convinced to just keep the current name as in your example. 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? Definitely. There are for example enumerated sets in Sage where even just deciding whether the set is finite or not is only semi-decidable; so implementing count would be impossible. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
