Opened 8 years ago

Closed 8 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:

Status badges

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)

fixing_shuffle_product_cb.patch​ (1.1 KB) - added by chrisjamesberg 8 years ago.
trac_14121_review-fc.patch​ (1.0 KB) - added by chapoton 8 years ago.

Download all attachments as: .zip

Change History (10)

Changed 8 years ago by chrisjamesberg

comment:1 Changed 8 years ago by chrisjamesberg

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by vdelecroix

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

comment:3 Changed 8 years ago by darij

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 8 years ago by chapoton

comment:4 Changed 8 years ago by chapoton

Here is a doctest.

comment:5 Changed 8 years ago by ncohen

  • 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: Changed 8 years ago by darij

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 8 years ago by ncohen

  • Status changed from needs_review to positive_review

HMmmmmmmmmmm... Well, then until we find a better way out ... :-)

Nathann

comment:8 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.8.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.