Hi Anne, Andrew,
Thanks for the hints. I hadn't noticed the magic incantation with
max_slope and length; that's the kind of thing I was looking for.
There seems to be quite a bit of overhead involved. Here are some
timings, where mypartitions() is a naive implementation of an
algorithm due to Boyer [1], see below.
sage: time mypartitions(130, 15)
Time: CPU 0.00 s, Wall: 0.00 s
sage: time mypartitions(140, 15)
Time: CPU 0.01 s, Wall: 0.01 s
sage: time mypartitions(150, 15)
Time: CPU 0.02 s, Wall: 0.02 s
sage: time mypartitions(160, 15)
Time: CPU 0.12 s, Wall: 0.12 s
sage: time mypartitions(170, 15)
Time: CPU 0.43 s, Wall: 0.43 s
sage: time mypartitions(180, 15)
Time: CPU 1.49 s, Wall: 1.49 s
sage: time p = Partitions(130, max_slope=-1, length=15).list()
Time: CPU 0.05 s, Wall: 0.05 s
sage: time p = Partitions(140, max_slope=-1, length=15).list()
Time: CPU 0.47 s, Wall: 0.47 s
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 3.43 s, Wall: 3.44 s
sage: time p = Partitions(160, max_slope=-1, length=15).list()
Time: CPU 18.20 s, Wall: 18.25 s
sage: time p = Partitions(170, max_slope=-1, length=15).list()
Time: CPU 77.37 s, Wall: 77.62 s
sage: time p = Partitions(180, max_slope=-1, length=15).list()
Time: CPU 277.75 s, Wall: 278.64 s
It's not a completely fair comparison, since mypartitions() does not
create the list of all partitions with the desired properties, but
rather generates them and then throws them away. Nevertheless, it
seems like a big gap.
Here is the mypartitions() code:
def GenP(A, n, k, korig, ell):
if (k == 1):
A[k] = n
# the partition is now in A, do whatever you want with it, e.g.
# print A.values()
else:
h = n/k - (k-1)/2
# print n, k, ell, h
for i in range(ell, h+1):
A[k] = i
GenP(A, n-i, k-1, korig, i+1)
def mypartitions(n, k):
A = dict()
GenP(A, n, k, k, 1)
It is just a straightforward implementation (that can undoubtedly be
optimized) of the algorithm from
[1] J.M.Boyer, Simple constant amortized time generation of fixed
length numeric partitions, J. Algorithms 54 (2005), 31-39.
--
Best,
Alex
--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
http://aghitza.org
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
