#5243: [with patch, needs work] non decreasing parking functions (depend now on
5255)
---------------------------+------------------------------------------------
Reporter: hivert | Owner: hivert
Type: enhancement | Status: assigned
Priority: minor | Milestone: sage-combinat
Component: combinatorics | Keywords: parking functions / Dyck words
---------------------------+------------------------------------------------
Comment(by ddrake):
I am working on reviewing this, and I have a couple questions and one
larger concern. First, some questions. I'm just curious about these
things:
* what does the {...@classmethod}}} decorator do?
* why does the {{{keys}}} method return the domain of the function? It
seems strange to have a {{{keys}}} method for something list-based, and
not dictionary-based.
Here are my concerns:
* Your code does not check to see if it gets a list of positive
integers, so you can do {{{NonDecreasingParkingFunction[[0, .1, pi/3,
sqrt(2)])}}}, yikes! Do we want to require lists of positive integers?
* In {{{is_a()}}}, you have:
{{{
for i in range(len(x)-1):
if x[i] > x[i+1] or x[i] > i+1:
return False
}}}
Instead of iterating over indices and doing a list lookup every time,
would it be faster to use Python's {{{enumerate}}} in something like this?
{{{
prev = 1
for i, elt in enumerate(x):
if prev > elt or elt > i+1:
return False
prev = elt
}}}
That would also let you finish the function with {{{return True}}},
since the {{{enumerate}}} loop would check the final element.
* Right now when you give the {{{NonDecreasingParkingFunction}}}
constructor a bad list, I see a strange error message:
{{{
sage: NonDecreasingParkingFunction([1,1,4])
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (5, 0))
---------------------------------------------------------------------------
AssertionError Traceback (most recent call
last)
/home/drake/.sage/temp/klee/10186/_home_drake__sage_init_sage_0.py in
<module>()
/var/tmp/sage-3.4.2/local/lib/python2.5/site-
packages/sage/combinat/non_decreasing_parking_function.pyc in
__init__(self, lst)
383 [1, 1, 2, 2, 5, 6]
384 """
--> 385 assert(is_a(lst))
386 CombinatorialObject.__init__(self, lst)
387
AssertionError:
}}}
* Also, related to {{{is_a}}}: the {{{assert}}} statement should give
the user some idea of what has gone wrong. I suggest changing the assert
line (line 409) to {{{assert is_a(lst), 'list is not a non-decreasing
parking function.'}}}. Also note that {{{assert}}} is a statement, not a
function -- just like {{{print}}} before Python 3.0.
* My biggest concern is with the getitem stuff. You are effectively
shifting the list indices by 1, which really bothers me. Perhaps other
people don't feel this way, and perhaps this is the best decision, but
whenever I am thinking of something as a list, I ''really'' want the
indices to be zero-based, since that's what the rest of Sage/Python does.
Right now, we have:
{{{
sage: f = NonDecreasingParkingFunction([1,1,2,3])
sage: f[2]
1
sage: f[3]
2
}}}
When I use square brackets, I'm thinking "list index", and I really
want it zero-based. Perhaps we should make these objects callable, so we
can treat them like functions? I would not mind having {{{f(2)}}} be 1 and
{{{f(3)}}} be 2, since the round parentheses indicate a function call, and
indeed the above object f is a function that sends 3 to 2.
I'm marking this "needs work" because of the list index issue. I have a
patch which fixes a bunch of tiny docstring bits which I'll upload once we
have the rest of this sorted out.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5243#comment:9>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
