Re: [sage-combinat-devel] partitions
Hi Alex, The best/easiest way is probably to use the max_slope option for Partitions: sage: Partitions(16,max_slope=-1)[:] [[16], [15, 1], [14, 2], [13, 3], [13, 2, 1], [12, 4], [12, 3, 1], [11, 5], [11, 4, 1], [11, 3, 2], [10, 6], [10, 5, 1], [10, 4, 2], [10, 3, 2, 1], [9, 7], [9, 6, 1], [9, 5, 2], [9, 4, 3], [9, 4, 2, 1], [8, 7, 1], [8, 6, 2], [8, 5, 3], [8, 5, 2, 1], [8, 4, 3, 1], [7, 6, 3], [7, 6, 2, 1], [7, 5, 4], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2], [6, 4, 3, 2, 1]] Cheers, Andrew -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To view this discussion on the web visit https://groups.google.com/d/msg/sage-combinat-devel/-/muZq70Aamw4J. 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.
Re: [sage-combinat-devel] partitions
Oops, sorry I didn't see your length requirement: sage: Partitions(16,max_slope=-1, length=4)[:] [[10, 3, 2, 1], [9, 4, 2, 1], [8, 5, 2, 1], [8, 4, 3, 1], [7, 6, 2, 1], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2]] sage: Partitions(10,max_slope=-1, length=3)[:] [[7, 2, 1], [6, 3, 1], [5, 4, 1], [5, 3, 2]] Andrew On Friday, 14 December 2012 20:15:49 UTC+11, Andrew Mathas wrote: Hi Alex, The best/easiest way is probably to use the max_slope option for Partitions: sage: Partitions(16,max_slope=-1)[:] [[16], [15, 1], [14, 2], [13, 3], [13, 2, 1], [12, 4], [12, 3, 1], [11, 5], [11, 4, 1], [11, 3, 2], [10, 6], [10, 5, 1], [10, 4, 2], [10, 3, 2, 1], [9, 7], [9, 6, 1], [9, 5, 2], [9, 4, 3], [9, 4, 2, 1], [8, 7, 1], [8, 6, 2], [8, 5, 3], [8, 5, 2, 1], [8, 4, 3, 1], [7, 6, 3], [7, 6, 2, 1], [7, 5, 4], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2], [6, 4, 3, 2, 1]] Cheers, Andrew -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To view this discussion on the web visit https://groups.google.com/d/msg/sage-combinat-devel/-/p637RNmLhOcJ. 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.
Re: [sage-combinat-devel] Re: problems with documentation build
This is the following issue: http://docs.mathjax.org/en/v1.1-latest/installation.html#firefox-and-local-fonts I do have stix fonts installed in the OS (Fedora 18) and equations render fine. If I uninstall stix-fonts then I get the [Math Processing Error]. Apparently they are only included from OS X 10.7 onward. At http://www.mathjax.org/help/fonts/ there are detailed instructions for how to install stix fonts manually. On Thursday, December 13, 2012 5:32:49 PM UTC, Dima Pasechnik wrote: I should mention that this kind of error was reported on http://trac.sagemath.org/sage_trac/ticket/13143 but nobody was able to say exactly where the problem lies. Now we know, it's Firefox-specific. I can also add that on OSX 10.5 with Firefox version 3.6.28 the situation is the same. Anyhow, the workaround ---use another browser--- is there... Best, Dima -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To view this discussion on the web visit https://groups.google.com/d/msg/sage-combinat-devel/-/gVJRov-4eU8J. 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.
[sage-combinat-devel] Re: problems with documentation build
On 2012-12-14, Volker Braun vbraun.n...@gmail.com wrote: --=_Part_97_13415008.1355485587298 Content-Type: text/plain; charset=ISO-8859-1 This is the following issue: http://docs.mathjax.org/en/v1.1-latest/installation.html#firefox-and-local-fonts I do have stix fonts installed in the OS (Fedora 18) and equations render fine. If I uninstall stix-fonts then I get the [Math Processing Error]. Apparently they are only included from OS X 10.7 onward. At http://www.mathjax.org/help/fonts/ there are detailed instructions for how to install stix fonts manually. I just checked, installing these fonts indeed fixes the issue on OSX 10.6.8. Thanks! Dima -- 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.
Re: [sage-combinat-devel] Re: problems with documentation build
Yes, cool! This works! Thanks so much, Anne On 12/14/12 3:46 AM, Volker Braun wrote: This is the following issue: http://docs.mathjax.org/en/v1.1-latest/installation.html#firefox-and-local-fonts I do have stix fonts installed in the OS (Fedora 18) and equations render fine. If I uninstall stix-fonts then I get the [Math Processing Error]. Apparently they are only included from OS X 10.7 onward. At http://www.mathjax.org/help/fonts/ there are detailed instructions for how to install stix fonts manually. On Thursday, December 13, 2012 5:32:49 PM UTC, Dima Pasechnik wrote: I should mention that this kind of error was reported on http://trac.sagemath.org/sage_trac/ticket/13143 http://trac.sagemath.org/sage_trac/ticket/13143 but nobody was able to say exactly where the problem lies. Now we know, it's Firefox-specific. I can also add that on OSX 10.5 with Firefox version 3.6.28 the situation is the same. Anyhow, the workaround ---use another browser--- is there... Best, Dima -- 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.
Re: [sage-combinat-devel] Partition options and cleanup patch
Hi Andrew, On Tue, Dec 11, 2012 at 01:31:28AM -0800, Andrew Mathas wrote: AH, I guess that reverse lexicographic is ambiguous as it could mean either reading the words in the reverse order or simply reversing the partial order. FWIW, In commutative algebra, and about term orders, they often use: inverse lexicographic (read the word right to left) negative lexicographic (reversing the partial order) reverse lexicographic == negative inverse lexicographic See e.g.: http://www.sagemath.org/doc/reference/sage/rings/polynomial/term_order.html Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
Re: [sage-combinat-devel] partitions
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.
Re: [sage-combinat-devel] partitions
Hi Alex, On Sat, Dec 15, 2012 at 09:04:40AM +1100, Alex Ghitza wrote: 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. ... 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. The theoretically complexity of the generic algorithm behind the scene is the same (CAT). A big part of the constant time factor should disappear once the generic algorithm will be Cythoned. Here, I also suspect that quite some time is spent transforming list's into actual partition's; again this should disappear once partition's will be Cythoned. I could not give you a time line however. If you don't absolutely need speed, I would just use the generic algorithm. That's will be one less thing to refactor when the optimization time will finally come. Cheers, Nicolas -- Nicolas M. Thiéry Isil nthi...@users.sf.net http://Nicolas.Thiery.name/ -- 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.
Re: [sage-combinat-devel] partitions
Hey Alexm
On Sat, Dec 15, 2012 at 09:04:40AM +1100, Alex Ghitza wrote:
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.
...
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.
The theoretically complexity of the generic algorithm behind the scene
is the same (CAT). A big part of the constant time factor should
disappear once the generic algorithm will be Cythoned. Here, I also
suspect that quite some time is spent transforming list's into actual
partition's; again this should disappear once partition's will be
Cythoned. I could not give you a time line however.
If you don't absolutely need speed, I would just use the generic
algorithm. That's will be one less thing to refactor when the
optimization time will finally come.
I ran %prun on the partitions of 150 and there is a large amount of time
spent in the infinity element constructor, calling isinstance, and the
rightmost_pivot. Here's the exact data I got below:
5884054 function calls in 76.544 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
507078 20.2530.000 37.5670.000
infinity.py:883(_element_constructor_)
43495 16.2810.000 16.2810.000 {isinstance}
50967.3500.001 53.8610.011
integer_list.py:192(rightmost_pivot)
5070784.2210.0004.2210.000 infinity.py:942(__init__)
2571613.7090.0006.0720.000 infinity.py:956(__cmp__)
1081962.9410.000 12.1960.000 {min}
479562.3020.000 13.3950.000 infinity.py:377(_mul_)
50962.0160.000 22.4180.004 integer_list.py:38(first)
1081961.9700.000 17.1710.000 integer_list.py:355(lambda)
1060741.8920.0006.9960.000 {max}
1561681.8810.0004.4360.000 integer_list.py:1034(lambda)
1561681.8010.0002.5550.000 integer_list.py:991(ceiling)
711.3470.0002.1160.000 infinity.py:285(__cmp__)
2775611.3400.0001.3400.000 {len}
1112001.2800.0001.8040.000 integer_list.py:972(floor)
581471.0300.0001.7130.000 infinity.py:1232(_neg_)
50960.4550.000 77.5160.015 integer_list.py:318(next)
581470.3850.0000.3850.000 infinity.py:820(gen)
...
I believe the calls to the infinity methods comes from the min_slope being
-infinity (and a similar issue could arise for max_slope). I've written a
small test patch (after #13605) which just setting the slopes to None (and
doing the appropriate checks) if no option is passed in and does the same
for max_length. I get about a 2x speedup, and there's likely more to be
gained if we do the same for max_part:
Also before #13605 is applied:
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 12.99 s, Wall: 15.03 s
With just #13605:
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 13.36 s, Wall: 14.01 s
With speedup patch:
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 6.36 s, Wall: 6.62 s
Data with speedup patch:
3000524 function calls (3000520 primitive calls) in 35.036 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
2041147.0610.000 13.1930.000
infinity.py:883(_element_constructor_)
685485.4880.0005.4880.000 {isinstance}
50963.2040.001 15.6250.003
integer_list.py:200(rightmost_pivot)
1081962.8110.000 11.0620.000 {min}
50961.8070.000 20.0200.004 integer_list.py:44(first)
1081961.8060.000 15.5410.000 integer_list.py:366(lambda)
1561681.6780.0002.3320.000 integer_list.py:1080(ceiling)
2041141.6570.0001.6570.000 infinity.py:942(__init__)
1561681.5470.0003.8790.000 integer_list.py:1123(lambda)
1112001.2130.0001.6970.000 integer_list.py:1061(floor)
2775621.1850.0001.1850.000 {len}
1081990.9800.0001.4500.000 infinity.py:956(__cmp__)
479560.7420.0002.6060.000 infinity.py:1049(_sub_)
479570.7220.0001.1960.000 infinity.py:1232(_neg_)
581320.5470.0002.0040.000 integer_list.py:359(lambda)
479570.5050.0000.8010.000 infinity.py:285(__cmp__)
479560.4220.0000.6680.000
