Opened 10 years ago

Closed 10 years ago

#12997 closed defect (fixed)

LyndonWords from composition beginning by 0's

Reported by: Adrien Brochier Owned by: Sage Combinat CC user
Priority: minor Milestone: sage-5.9
Component: combinatorics Keywords: lyndon words, sage-combinat, days45
Cc: Sébastien Labbé, Franco Saliola Merged in: sage-5.9.beta1
Authors: Adrien Brochier Reviewers: Travis Scrimshaw, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Frédéric Chapoton)

LyndonWords, when applied to a composition starting with 0's, gives a wrong result, e.g.:

for w in LyndonWords(list([0,1])):
    print w

return 1 instead of 2, and in a similar vein

for w in LyndonWords(list([0,2])):
    print w

return '12'

The problem is also described here : http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/5c4b691a692b56b0#

The problem is that necklace._sfc() ignores 0's at the begining of a list.

A modified lyndon_word.py file which fix the problem is attached.

Apply:

Attachments (5)

lyndon_word.py (12.4 KB) - added by Adrien Brochier 10 years ago.
Modified lyndon_word.py
diff (303 bytes) - added by Adrien Brochier 10 years ago.
diff
trac_12997-LyndonWords-compositions.patch (873 bytes) - added by Adrien Brochier 10 years ago.
patch
trac_12997-LyndonWords-review-ts.patch (1.2 KB) - added by Travis Scrimshaw 10 years ago.
trac_12997-Lyndon-review-fc.patch (1.5 KB) - added by Frédéric Chapoton 10 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 10 years ago by Adrien Brochier

Description: modified (diff)

Changed 10 years ago by Adrien Brochier

Attachment: lyndon_word.py added

Modified lyndon_word.py

Changed 10 years ago by Adrien Brochier

Attachment: diff added

diff

comment:2 Changed 10 years ago by Franco Saliola

Hello Adrien, can you post a patch with your changes instead of the .py file?

You can follow Sébastien's guide on http://thales.math.uqam.ca/~labbes/Sage/how-to-contribute/ How to contribute to Sage (especially steps 15 to 17).

comment:3 Changed 10 years ago by Franco Saliola

Cc: Sébastien Labbé Franco Saliola added

comment:4 Changed 10 years ago by Adrien Brochier

Status: newneeds_review

Changed 10 years ago by Adrien Brochier

patch

comment:5 Changed 10 years ago by Jeroen Demeyer

Please fill in your real name as Author.

comment:6 Changed 10 years ago by Adrien Brochier

Authors: Adrien Brochier

comment:7 Changed 10 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewneeds_work

Please add some tests to the __iter__ method showing the ticket has been fixed such as:

TESTS:

Showing :trac:`12997` is fixed::

    sage: LyndonWords([0,1]).list()
    [word: 2]
    sage: LyndonWords([0,2]).list()
    []
    sage: LyndonWords([0,0,1,0,1]).list()
    [word: 35]

Thanks,
Travis

Changed 10 years ago by Travis Scrimshaw

comment:8 Changed 10 years ago by Travis Scrimshaw

Keywords: days45 added
Status: needs_workneeds_review

I've attached the review patch which adds the doctests and tweaks the code format. Could someone give this a quick second review please?

Thanks,
Travis

Changed 10 years ago by Frédéric Chapoton

comment:9 Changed 10 years ago by Frédéric Chapoton

Description: modified (diff)
Status: needs_reviewpositive_review

Ok, this looks good to me.

I have added a patch to change the "raise" to python3 syntax

positive review

comment:10 Changed 10 years ago by Frédéric Chapoton

Reviewers: Travis ScrimshawTravis Scrimshaw, Frédéric Chapoton

comment:11 Changed 10 years ago by Travis Scrimshaw

Thanks Frederic!

comment:12 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.9.beta1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.