Ticket #6627 (closed defect: fixed)
[with patch, positive review] fix lyndon and standard factorization of words
| Reported by: | saliola | Owned by: | saliola |
|---|---|---|---|
| Priority: | major | Milestone: | sage-4.1.2 |
| Component: | combinatorics | Keywords: | |
| Cc: | slabbe | Work issues: | |
| Report Upstream: | Reviewers: | Vincent Delecroix | |
| Authors: | Franco Saliola | Merged in: | Sage 4.1.2.alpha0 |
| Dependencies: | Stopgaps: |
Description
The last 1 in the word disappeared:
sage: Word([1,2,1,3,1,2,1]).lyndon_factorization() (1213.12)
Lyndon factorization of the empty word should work.
sage: Words('01')('').lyndon_factorization()
Traceback (most recent call last):
...
StopIteration
The standard factorization of 321 is 32.1.
sage: sage: Word([3,2,1]).standard_factorization() (321.)
The standard factorization of the empty word should return the empty word, and not two copies of the empty word.
sage: Words('123')('').standard_factorization()
(.)
Attachments
Change History
Changed 4 years ago by saliola
-
attachment
trac_6627-lyndon_words_fix.patch
added
comment:1 Changed 4 years ago by saliola
- Summary changed from lyndon and standard factorization of words is broken to [with patch, needs review] fix lyndon and standard factorization of words
This new implementation is correct and also faster.
sage: sage: Word([1,2,1,3,1,2,1]).lyndon_factorization()
(1213, 12, 1)
sage: sage: Words('01')('').lyndon_factorization()
()
sage: sage: sage: Word([3,2,1]).standard_factorization()
(32, 1)
sage: sage: Words('123')('').standard_factorization()
()
I also changed the repr of the (word) Factorization class to use ',' instead of '.' because otherwise the period is confusing if you factor a long word:
sage: WordOptions(truncate_length=10) sage: tm = words.ThueMorseWord() sage: tm[:100].lyndon_factorization() (011, 01, 0011, 00101101, 0010110011..., 0010110011..., 0010110011..., 0010110011, 0)
comment:3 Changed 4 years ago by vdelecroix
- Summary changed from [with patch, needs review] fix lyndon and standard factorization of words to [with patch, positive review] fix lyndon and standard factorization of words
Note: See
TracTickets for help on using
tickets.

based on sage-4.1.1.alpha0