overlap_partion of a word should return an instance disjoint set data structure

[seblabbe]

When I coded the overlap_partition function in 2007, the purpose was to study equations on words. But, when the sage-words code was merged into sage in december 2008, the disjoint set data structure was not ready so that sage-words got merged without it. That is why overlap_partition returns a set of sets (and also why I don't use the function ever since then).

The disjoint set data structure got merged into sage recently : #6775. So this patch changes the behavior of overlap_partition to its initial goal.

BEFORE (sage-4.3.2):

sage: w = Words(range(10))(range(10))
sage: w.overlap_partition(w,3)
{{0, 9, 3, 6}, {1, 4, 7}, {8, 2, 5}}
sage: 
sage: type(_)
<class 'sage.sets.set.Set_object_enumerated'>

WITH THE PATCH:

The following example illustrates that a word that overlaps with itself has a period :

sage: w = Words(range(10))(range(10))
sage: p = w.overlap_partition(w, 3)
sage: type(p)
<type 'sage.sets.disjoint_set.DisjointSet_of_hashables'>
sage: d = p.element_to_root_dict()
sage: m = WordMorphism(d)
sage: print m
WordMorphism: 0->3, 1->4, 2->5, 3->3, 4->4, 5->5, 6->3, 7->4, 8->5, 9->3
sage: m(w)
word: 3453453453

The following example shows that if the image of a word under an involution f overlaps its square, then it is f-symmetric i.e. the product of two f-palindromes :

sage: W = Words([-11,-9,..,11])
sage: w = W([1,3,..,11])
sage: w
word: 1,3,5,7,9,11
sage: inv = lambda x:-x
sage: f = WordMorphism(dict( (a, inv(a)) for a in W.alphabet()))
sage: print f
WordMorphism: -1->1, -11->11, -3->3, -5->5, -7->7, -9->9, 1->-1, 11->-11, 3->-3, 5->-5, 7->-7, 9->-9
sage: p = (w*w).overlap_partition(f(w).reversal(), 2, involution=inv)
sage: m = WordMorphism(p.element_to_root_dict())
sage: m(w)
word: 1,-1,5,7,-7,-5
sage: m(w).is_symmetric(f)
True

CC: @sagetrac-abmasse

Component: combinatorics

Keywords: equation, words, partition

Author: Sébastien Labbé

Reviewer: Alexandre Blondin Massé

Merged: sage-4.3.4.alpha0

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

[sagetrac-abmasse]

comment:2

Hello, Sébastien !

I tested your patch and generated the documentation. I have some comments on the latter:

1. The first sentence appears kind of complicated.

   Returns the partition of the alphabet induced by the equivalence relation obtained
   from the symmetric, reflexive and transitive closure of the set of pairs of letters
   R_{self,other,delay}\cup p defined below.

I suggest something like:

Returns the partition over the alphabet induced by overlapping the words self
and other with given delay.

Then you give the formal definition and the example.

2. In the example, it is not clear how the words cheval and abcdef overlap. It could be better to use a constant width character font if possible.

3. You should give more details about what the involution is there for.

4. Same comment about parameter p. I prefer more significant name (in that case, maybe partition ?) and it would be nice to know what p is used for (I guess it's a partition corresponding to already equivalent letters ?)

That's all for now. The rest seems fine. As soon as you fix the documentation according to my comments, I'll resume the review.

[sagetrac-abmasse]

Changed keywords from none to equation, words, partition

[seblabbe]

comment:3

Attachment: trac_8318_overlap_partition-sl.patch.gz

I fixed the documentation. Needs review!

[sagetrac-abmasse]

comment:4

I'm done with the review. All tests passed, I corrected a minor error in the documentation. The code makes sense. Positive review.

[sagetrac-abmasse]

Attachment: trac_8313_review-abm.patch.gz

one-character review -- apply on top of the first patch

[sagetrac-abmasse]

Reviewer: Alexandre Blondin Massé

[sagetrac-abmasse]

Author: Sébastien Labbé

[sagetrac-mvngu]

comment:6

Merged in this order:

1. trac_8318_overlap_partition-sl.patch
2. trac_8313_review-abm.patch

[sagetrac-mvngu]

Merged: sage-4.3.4.alpha0