Opened 7 years ago
Closed 7 years ago
#14121 closed defect (fixed)
Fixing bug in shuffle product
Reported by: | chrisjamesberg | 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 7 years ago by
comment:1 Changed 7 years ago by
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
comment:3 Changed 7 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 7 years ago by
comment:4 Changed 7 years ago by
Here is a doctest.
comment:5 Changed 7 years ago by
- Reviewers changed from Franco Saliola to 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 7 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 in reply to: ↑ 6 Changed 7 years ago by
- Status changed from needs_review to positive_review
HMmmmmmmmmmm... Well, then until we find a better way out ... :-)
Nathann
comment:8 Changed 7 years ago by
- Merged in set to sage-5.8.rc0
- Resolution set to fixed
- Status changed from positive_review to 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