Fixing bug in shuffle product

[Chris Berg]

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

[Vincent Delecroix]

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

[Darij Grinberg]

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.

[Frédéric Chapoton]

Here is a doctest.

[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

[Darij Grinberg]

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

[Nathann Cohen]

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

Nathann