#11466: Adding turning_number() function to word paths
-----------------------------+----------------------------------------------
Reporter: abmasse | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.7.1
Component: combinatorics | Keywords: discrete path, turning number
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by tmonteil):
* status: needs_review => needs_work
Comment:
Hi Alexandre,
first, you should define more precisely what is the turning number of a
discrete curve, since it is not a direct generalisation of the
[http://en.wikipedia.org/wiki/Winding_number#Turning_number turning
number] defined for smooth curves to discrete ones. When the discrete
curve turns by pi/2 or -pi/2, then there is a canonical way to smooth it,
and in this case your construction yields the good number 1/4 or -1/4. But
when the discrete curve turns back (what you call an opposite step), there
are two different ways to smooth it to get a turning number of 1/2 or
-1/2. What you are doing with the `remove_opposite_steps()` method is to
choose one of them, in a way that is not local. Think to `luuuddl` and
`luuuddr`: in the first case, your algorithm considers that the curve
turned by +pi at the top extremity, whereas in the second case, it
considers that the curve turned by -pi. Hence, you should explain more, or
give a reference.
Second, your method `remove_opposite_steps()` is far from optimal since it
builds a lot of lists/words during the process (a part of `w` is copied
many times). You should only modify the extremities of the lists/words
`left` and `right`, with a constant cost at each loop.
For example, i quickly tried this (the variables `i` and `length` may be
renamed, and there may be a way to avoid transforming the word into a list
to use the `pop()` method):
{{{
def rr(self):
a,b,A,B = self.parent().alphabet()
opposite_steps = [[a,A], [A,a], [b,B], [B,b]]
i = 0
left = []
right = list(self.reversal())
length = len(right)
while length != 0:
if i !=0 and [left[-1],right[-1]] in opposite_steps:
left.pop()
right.pop()
i -= 1
length -= 1
else:
left.append(right.pop())
i += 1
length -= 1
return self.parent()(left)
}}}
The results are:
{{{
sage: Freeman = WordPaths(Integers(4))
sage: timeit('Freeman(words.RandomWord(10000,4)).remove_opposite_steps()')
5 loops, best of 3: 2.54 s per loop
sage: timeit('Freeman(words.RandomWord(10000,4)).rr()')
5 loops, best of 3: 139 ms per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11466#comment:2>
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.
