#8318: overlap_partion of a word should return an instance disjoint set data
structure
-----------------------------+----------------------------------------------
Reporter: slabbe | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.3.3
Component: combinatorics | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
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
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8318>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
