Bad behavior of is_square_free for Words

[videlec]

The method is_square_free of sage.combinat.words.word.Word returns the wrong value in special cases (including squares !)

sage: Word("aa").is_square_free()  # the funniest
True
sage: Word("baa").is_square_free()
True
sage: Word("cbaa").is_square_free()
True
sage: Word("dcbaa").is_square_free()
True

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: word

Author: Vincent Delecroix, Sébastien Labbé

Reviewer: Mike Hansen, Nathann Cohen

Merged: sage-4.4.4.alpha0

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

[mwhansen]

Reviewer: Mike Hansen

[mwhansen]

Changed author from vdelecroix to Vincent Delecroix

[mwhansen]

comment:3

Looks good to me.

[videlec]

comment:4

Oups, intersection with #8429 which refactors the code of sage.combinat.words.

I post soon a new patch that apply only after #8429 and I think it's better.

[videlec]

another one-line correction that applies after #8429

[videlec]

Attachment: trac_8490-square_free-vd.2.patch.gz

another one-line correction that applies after #8429

[videlec]

Attachment: trac_8490-square_free-vd.3.patch.gz

Apply only this

[seblabbe]

comment:5

Attachment: trac_8490-square_free-vd.patch.gz

The same bug was occuring with is_cube_free :

sage: Word('111').is_cube_free()
True
sage: Word('2111').is_cube_free()
True
sage: Word('32111').is_cube_free()
True

I just applied a patch which fixes this problem. I changed some doctests of both is_square_free and is_cube_free. I also removed a useless slice in the code of both functions and this gives good improvements in timings :

BEFORE:

sage: t = words.ThueMorseWord()
sage: %timeit t[:100].is_cube_free()
5 loops, best of 3: 3.13 s per loop

AFTER:

sage: t = words.ThueMorseWord()
sage: %timeit t[:100].is_cube_free()
5 loops, best of 3: 1.18 s per loop

[seblabbe]

Applies over the precedent patch

[seblabbe]

comment:6

Attachment: trac_8490_review-sl.patch.gz

[seblabbe]

Changed author from Vincent Delecroix to Vincent Delecroix, Sébastien Labbé

[nathanncohen]

comment:7

Hello !! This patch is finem except for a small unimportant thing which bothered me :

for end in xrange(start+3, L+1, 3): 

Why go up to L+1 when the last letter is L-1 ? The algorithm is still correct as

Word("abc")[:50000]

raises no exception, but as there is no reason to.... So I give a positive review to the patches above, and trac_8490_review-ncohen.patch is left to be reviewed by anyone other than me (quoting Minh) :-)

Thank you for this patch !!

Nathann

[nathanncohen]

comment:8

The patches are to be applied in this order :

• trac_8490-square_free-vd.patch
• trac_8490_review-sl.patch
• trac_8490_review-ncohen.patch

Nathann

[seblabbe]

comment:9

Replying to @nathanncohen:

Hello !! This patch is finem except for a small unimportant thing which bothered me :

for end in xrange(start+3, L+1, 3): 

Why go up to L+1 when the last letter is L-1 ?

First, xrange returns a left-closed and right-open interval. Hence, one needs to write something like xrange(0,L+1) if one wants to go up to L :

sage: list(xrange(0,5))
[0, 1, 2, 3, 4]

Second, the variable end is not used to get a specific item in self but for slicing self. Hence, if one wants to consider all the slicing possibilities, the variable end must take the last possible value L:

sage: list(xrange(0,5)) [2:5]   #is good
[2, 3, 4]
sage: list(xrange(0,5)) [2:4]   #forgets the last letter
[2, 3]

Hence, your patch is strange in the sense that doctests should not pass!

The algorithm is still correct as

Word("abc")[:50000]

raises no exception, but as there is no reason to....

We made the choice of following the Python behavior for slices that goes too far:

sage: L = range(10)
sage: L
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: L[:100]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Sébastien

[seblabbe]

comment:10

Replying to @nathanncohen:

The patches are to be applied in this order :

• trac_8490-square_free-vd.patch
• trac_8490_review-sl.patch
• trac_8490_review-ncohen.patch

Nathann

The patch trac_8490_review-ncohen.patch reintroduce the same bug as the current ticket is trying to solve. Hence, I think the patches are to be reviewed in this order again :

• trac_8490-square_free-vd.patch
• trac_8490_review-sl.patch

Sébastien

[nathanncohen]

comment:11

Perfectly right !! sorryyyyyyyyyyy !!! :-)

Nathann

[nathanncohen]

comment:12

Well, then short of this, which was my mistake, I noticed nothing wrong with these two patches ! :-)

Nathann

[mwhansen]

Changed reviewer from Mike Hansen to Mike Hansen, Nathann Cohen

[mwhansen]

Merged: sage-4.4.4.alpha0