Opened 10 years ago
Closed 10 years ago
#14121 closed defect (fixed)
Fixing bug in shuffle product
Reported by: | Chris Berg | Owned by: | Chris Berg |
---|---|---|---|
Priority: | major | Milestone: | sage-5.8 |
Component: | combinatorics | Keywords: | shuffle product, days45 |
Cc: | Merged in: | sage-5.8.rc0 | |
Authors: | Chris Berg | Reviewers: | Franco Saliola, Frédéric Chapoton, Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Shuffle product contains method does not work properly.
sage: w = Word('ab') sage: x = Word('ac') sage: w.shuffle(x) Shuffle product of word: ab and word: ac sage: s = w.shuffle(x) sage: s.list() [word: abac, word: aabc, word: aacb, word: aabc, word: aacb, word: acab] sage: x*w in s False
Attachments (2)
Change History (10)
Changed 10 years ago by
Attachment: | fixing_shuffle_product_cb.patch added |
---|
comment:1 Changed 10 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
Theorem 7 in http://www8.cs.umu.se/research/uminf/reports/2011/001/part1.pdf seems relevant to finding a polynomial-time algorithm for this. Just mentioning.
Changed 10 years ago by
Attachment: | trac_14121_review-fc.patch added |
---|
comment:5 Changed 10 years ago by
Reviewers: | Franco Saliola → Franco Saliola, Frédéric Chapoton, Nathann Cohen |
---|
Hellooooooooooooooooooo !!
Well, this patch definitely fixes a bug and is only slower ono the instances for which it gave bad answers... I think that it's good to go ! What would you think of adding a .. TODO
in the method's docstring saying that the pdf given above contains the recipe for an efficient future new implementation of that method ?
Whether you chose to add this comment or not, feel free to set this ticket to positive_review
once you are set :-)
Nathann
comment:6 follow-up: 7 Changed 10 years ago by
Wait, wait -- I've never said it gives a more efficient solution; I said it "seems relevant". I fear it uses a constant-size alphabet, which is not what we want...
comment:7 Changed 10 years ago by
Status: | needs_review → positive_review |
---|
HMmmmmmmmmmm... Well, then until we find a better way out ... :-)
Nathann
comment:8 Changed 10 years ago by
Merged in: | → sage-5.8.rc0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Hi,
You should add a test that ensures you actually correct the thing ! However, it would be a good idea to actually rewrite the whole method.
Vincent