Fixing bug in shuffle product

[sagetrac-chrisjamesberg]

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

Component: combinatorics

Keywords: shuffle product, days45

Author: Chris Berg

Reviewer: Franco Saliola, Frédéric Chapoton, Nathann Cohen

Merged: sage-5.8.rc0

Issue created by migration from https://trac.sagemath.org/ticket/14121

[sagetrac-chrisjamesberg]

comment:1

Attachment: fixing_shuffle_product_cb.patch.gz

[videlec]

comment:2

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

[darijgr]

comment:3

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.

[fchapoton]

Attachment: trac_14121_review-fc.patch.gz

[fchapoton]

comment:4

Here is a doctest.

[nathanncohen]

comment:5

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

[nathanncohen]

Changed reviewer from Franco Saliola to Franco Saliola, Frédéric Chapoton, Nathann Cohen

[darijgr]

comment:6

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...

[nathanncohen]

comment:7

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

Nathann

[jdemeyer]

Merged: sage-5.8.rc0