Sage: Ticket #17920: Reimplement IntegerLists using Polyhedron.integral_points()
https://trac.sagemath.org/ticket/17920
<p>
This fixes <a class="closed ticket" href="https://trac.sagemath.org/ticket/17548" title="defect: Partitions() is buggy (closed: duplicate)">#17548</a>.
</p>
<p>
It also adds new features to <code>IntegerLists</code>:
</p>
<ol><li>Negative integers are allowed (but the default still is <code>min_part=0</code>).
</li></ol><ol start="2"><li>There does not need to be a fixed sum, one can do for example <code>IntegerLists(max_part=2)</code> for all lists of integers <= 2. One can also give a lower/upper bound for the sum.
</li></ol><p>
Note that the current implementation requires, for a given length, that there are only finitely many lists of that length. This limitation could be lifted in the future.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17920
Trac 1.1.6ncohenMon, 09 Mar 2015 17:57:19 GMTcc set
https://trac.sagemath.org/ticket/17920#comment:1
https://trac.sagemath.org/ticket/17920#comment:1
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
</ul>
TicketjdemeyerMon, 09 Mar 2015 20:56:34 GMTstatus, milestone changed; resolution set
https://trac.sagemath.org/ticket/17920#comment:2
https://trac.sagemath.org/ticket/17920#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>invalid</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.6</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
The Sage MILP solvers cannot enumerate all solutions => closing as invalid.
</p>
TicketjdemeyerTue, 10 Mar 2015 15:41:56 GMTstatus, summary, milestone changed; resolution deleted
https://trac.sagemath.org/ticket/17920#comment:3
https://trac.sagemath.org/ticket/17920#comment:3
<ul>
<li><strong>status</strong>
changed from <em>closed</em> to <em>new</em>
</li>
<li><strong>summary</strong>
changed from <em>Reimplement IntegerLists using MILP</em> to <em>Reimplement IntegerLists using Polyhedron.integral_points()</em>
</li>
<li><strong>resolution</strong>
<em>invalid</em> deleted
</li>
<li><strong>milestone</strong>
changed from <em>sage-duplicate/invalid/wontfix</em> to <em>sage-6.6</em>
</li>
</ul>
TicketjdemeyerWed, 11 Mar 2015 21:49:28 GMTbranch set
https://trac.sagemath.org/ticket/17920#comment:4
https://trac.sagemath.org/ticket/17920#comment:4
<ul>
<li><strong>branch</strong>
set to <em>u/jdemeyer/ticket/17920</em>
</li>
</ul>
TicketncohenThu, 12 Mar 2015 07:16:35 GMTcommit set
https://trac.sagemath.org/ticket/17920#comment:5
https://trac.sagemath.org/ticket/17920#comment:5
<ul>
<li><strong>commit</strong>
set to <em>492696fb8bbca610dd8b5415b44910196e9d9222</em>
</li>
</ul>
<p>
I do not understand what this is... Did you copy/paste the original file? It seems that you copy/pasted the original files and made some modifications to it <code>O_o</code>
</p>
<p>
Nathann
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=492696fb8bbca610dd8b5415b44910196e9d9222"><span class="icon"></span>492696f</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketjdemeyerThu, 12 Mar 2015 10:02:39 GMT
https://trac.sagemath.org/ticket/17920#comment:6
https://trac.sagemath.org/ticket/17920#comment:6
<p>
Yes, that's what I did. Anyway, this is still very much work in progress...
</p>
TicketncohenThu, 12 Mar 2015 10:03:35 GMT
https://trac.sagemath.org/ticket/17920#comment:7
https://trac.sagemath.org/ticket/17920#comment:7
<blockquote class="citation">
<p>
Yes, that's what I did. Anyway, this is still very much work in progress...
</p>
</blockquote>
<p>
Oh, okay!
</p>
<p>
Nathann
</p>
TicketjdemeyerThu, 12 Mar 2015 15:41:45 GMTdependencies set
https://trac.sagemath.org/ticket/17920#comment:8
https://trac.sagemath.org/ticket/17920#comment:8
<ul>
<li><strong>dependencies</strong>
set to <em>#17937</em>
</li>
</ul>
TicketgitThu, 12 Mar 2015 16:41:59 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:9
https://trac.sagemath.org/ticket/17920#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>492696fb8bbca610dd8b5415b44910196e9d9222</em> to <em>5896b1160e7dd123abfc03325583ffe805d0912b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=eb6ba858894c3c3f77b2278115198bfe9076adf0"><span class="icon"></span>eb6ba85</a></td><td><code>Fix integral_points() for polyhedra in 0 dimensions</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5896b1160e7dd123abfc03325583ffe805d0912b"><span class="icon"></span>5896b11</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketgitFri, 13 Mar 2015 10:38:04 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:10
https://trac.sagemath.org/ticket/17920#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>5896b1160e7dd123abfc03325583ffe805d0912b</em> to <em>c835117a1e14e84d3f823b4111a092a80b4c3ef4</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c835117a1e14e84d3f823b4111a092a80b4c3ef4"><span class="icon"></span>c835117</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketgitSat, 14 Mar 2015 14:11:46 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:11
https://trac.sagemath.org/ticket/17920#comment:11
<ul>
<li><strong>commit</strong>
changed from <em>c835117a1e14e84d3f823b4111a092a80b4c3ef4</em> to <em>755b67a1c9516bcd44f59aab6a8b6032d257591d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=755b67a1c9516bcd44f59aab6a8b6032d257591d"><span class="icon"></span>755b67a</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketjdemeyerSat, 14 Mar 2015 14:17:41 GMT
https://trac.sagemath.org/ticket/17920#comment:12
https://trac.sagemath.org/ticket/17920#comment:12
<p>
This now seems to work reasonably well. Not yet ready, but good enough for example to compare with the existing implementation. That's how I found all the bugs at <a class="closed ticket" href="https://trac.sagemath.org/ticket/17548" title="defect: Partitions() is buggy (closed: duplicate)">#17548</a>.
</p>
<p>
Due to the polyhedra overhead, it is generally (a lot) slower than the existing code.
</p>
TicketncohenSat, 14 Mar 2015 16:40:08 GMT
https://trac.sagemath.org/ticket/17920#comment:13
https://trac.sagemath.org/ticket/17920#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:12" title="Comment 12">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
This now seems to work reasonably well. Not yet ready, but good enough for example to compare with the existing implementation. That's how I found all the bugs at <a class="closed ticket" href="https://trac.sagemath.org/ticket/17548" title="defect: Partitions() is buggy (closed: duplicate)">#17548</a>.
</p>
<p>
Due to the polyhedra overhead, it is generally (a lot) slower than the existing code.
</p>
</blockquote>
<p>
Is it worth changing this branch so that it changes the existing code instead of adding a new file ? As you said: let's be correct first, *then* fast.
</p>
<p>
Nathann
</p>
TicketjdemeyerSat, 14 Mar 2015 16:43:59 GMT
https://trac.sagemath.org/ticket/17920#comment:14
https://trac.sagemath.org/ticket/17920#comment:14
<p>
My code does not yet support all (undocumented!) features of the old <code>IntegerListsLex</code>, so we cannot yet replace <code>IntegerListsLex</code>.
</p>
TicketgitSat, 14 Mar 2015 18:24:59 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:15
https://trac.sagemath.org/ticket/17920#comment:15
<ul>
<li><strong>commit</strong>
changed from <em>755b67a1c9516bcd44f59aab6a8b6032d257591d</em> to <em>674a518d20e6b220f668d88ec748376217b243da</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=674a518d20e6b220f668d88ec748376217b243da"><span class="icon"></span>674a518</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketgitSat, 14 Mar 2015 22:03:17 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:16
https://trac.sagemath.org/ticket/17920#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>674a518d20e6b220f668d88ec748376217b243da</em> to <em>4e5dbaec98f2d779a6c73a69d5b71581be7fb5da</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4e5dbaec98f2d779a6c73a69d5b71581be7fb5da"><span class="icon"></span>4e5dbae</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketjdemeyerSat, 14 Mar 2015 22:05:21 GMT
https://trac.sagemath.org/ticket/17920#comment:17
https://trac.sagemath.org/ticket/17920#comment:17
<p>
This now implements <code>Compositions</code> using my new <code>IntegerListsLex</code> (is the lex ordering really important? I guess not, it's for sure nowhere documented). However, doing the same for <code>Partitions</code> leads to all kinds of breakage and I don't understand why.
</p>
TicketgitSat, 14 Mar 2015 22:11:32 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:18
https://trac.sagemath.org/ticket/17920#comment:18
<ul>
<li><strong>commit</strong>
changed from <em>4e5dbaec98f2d779a6c73a69d5b71581be7fb5da</em> to <em>c0772f8981d3856bdf85cb3eb07094944aa73262</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c0772f8981d3856bdf85cb3eb07094944aa73262"><span class="icon"></span>c0772f8</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketgitSat, 14 Mar 2015 22:23:21 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:19
https://trac.sagemath.org/ticket/17920#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>c0772f8981d3856bdf85cb3eb07094944aa73262</em> to <em>631c47652412b518bb4bcd8cb4465a4fbfe16a83</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=631c47652412b518bb4bcd8cb4465a4fbfe16a83"><span class="icon"></span>631c476</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketgitSun, 15 Mar 2015 11:06:18 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:20
https://trac.sagemath.org/ticket/17920#comment:20
<ul>
<li><strong>commit</strong>
changed from <em>631c47652412b518bb4bcd8cb4465a4fbfe16a83</em> to <em>3b7f4cd93be25051cc9ecf08d573b2aacdc02010</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3b7f4cd93be25051cc9ecf08d573b2aacdc02010"><span class="icon"></span>3b7f4cd</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketgitSun, 15 Mar 2015 11:19:28 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:21
https://trac.sagemath.org/ticket/17920#comment:21
<ul>
<li><strong>commit</strong>
changed from <em>3b7f4cd93be25051cc9ecf08d573b2aacdc02010</em> to <em>936a2c73d3612c76cf115d1b5dd690417e6ce4ab</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=936a2c73d3612c76cf115d1b5dd690417e6ce4ab"><span class="icon"></span>936a2c7</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketjdemeyerSun, 15 Mar 2015 11:22:05 GMTcc changed
https://trac.sagemath.org/ticket/17920#comment:22
https://trac.sagemath.org/ticket/17920#comment:22
<ul>
<li><strong>cc</strong>
<em>aschilling</em> <em>tscrim</em> added
</li>
</ul>
<p>
Note that this changes 3 tests (just reordering the output) in <code>src/sage/tests/book_schilling_zabrocki_kschur_primer.py</code>
</p>
TicketjdemeyerSun, 15 Mar 2015 11:23:30 GMT
https://trac.sagemath.org/ticket/17920#comment:23
https://trac.sagemath.org/ticket/17920#comment:23
<p>
The code on this ticket is essentially complete, I just need to add more doctests to comply with the "coverage" policy.
</p>
TicketgitSun, 15 Mar 2015 12:38:47 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:24
https://trac.sagemath.org/ticket/17920#comment:24
<ul>
<li><strong>commit</strong>
changed from <em>936a2c73d3612c76cf115d1b5dd690417e6ce4ab</em> to <em>c9fa1c403feb7efb7b0c272b36e9062b3f0988d3</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c9fa1c403feb7efb7b0c272b36e9062b3f0988d3"><span class="icon"></span>c9fa1c4</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketgitSun, 15 Mar 2015 15:03:25 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:25
https://trac.sagemath.org/ticket/17920#comment:25
<ul>
<li><strong>commit</strong>
changed from <em>c9fa1c403feb7efb7b0c272b36e9062b3f0988d3</em> to <em>b0a04aa5a4454766ed9802d8e99abcd7fb3e105b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b0a04aa5a4454766ed9802d8e99abcd7fb3e105b"><span class="icon"></span>b0a04aa</a></td><td><code>Reimplement IntegerLists using Polyhedron.integral_points()</code>
</td></tr></table>
TicketjdemeyerSun, 15 Mar 2015 15:08:29 GMTstatus changed
https://trac.sagemath.org/ticket/17920#comment:26
https://trac.sagemath.org/ticket/17920#comment:26
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TickettscrimSun, 15 Mar 2015 15:25:29 GMT
https://trac.sagemath.org/ticket/17920#comment:27
https://trac.sagemath.org/ticket/17920#comment:27
<p>
Do you have some timings?
</p>
<p>
Also, both of these are wrong:
</p>
<pre class="wiki">sage: Compositions(3, max_length=2, inner=[1,1,1]).list()
[]
sage: Compositions(10, outer=[4], inner=[1,1]).list()
[]
</pre><p>
The first should be <code>[[2, 1], [1, 2]]</code> since the <code>inner</code> (or <code>outer</code>) are not related to the min or max lengths. For the second, the inner composition is extendedby the minimum part, so there are many such compositions, such as <code>[4,6]</code>, <code>[2,8]</code>, etc.
</p>
TicketvdelecroixSun, 15 Mar 2015 15:28:48 GMT
https://trac.sagemath.org/ticket/17920#comment:28
https://trac.sagemath.org/ticket/17920#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:27" title="Comment 27">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Do you have some timings?
</p>
</blockquote>
<p>
Slow is better than wrong, isn't it? ;-)
</p>
TicketjdemeyerSun, 15 Mar 2015 15:29:49 GMT
https://trac.sagemath.org/ticket/17920#comment:29
https://trac.sagemath.org/ticket/17920#comment:29
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:27" title="Comment 27">tscrim</a>:
</p>
<blockquote class="citation">
<p>
Do you have some timings?
</p>
</blockquote>
<p>
My code is much slower.
</p>
<blockquote class="citation">
<p>
Also, both of these are wrong:
</p>
<pre class="wiki">sage: Compositions(3, max_length=2, inner=[1,1,1]).list()
[]
sage: Compositions(10, outer=[4], inner=[1,1]).list()
[]
</pre><p>
The first should be <code>[[2, 1], [1, 2]]</code>
</p>
</blockquote>
<p>
I don't think so. The <code>Compositions</code> code explicitly adds the length of the <code>inner</code> argument as minimal length. I didn't change this.
</p>
TicketjdemeyerSun, 15 Mar 2015 15:31:09 GMTpriority changed
https://trac.sagemath.org/ticket/17920#comment:30
https://trac.sagemath.org/ticket/17920#comment:30
<ul>
<li><strong>priority</strong>
changed from <em>major</em> to <em>blocker</em>
</li>
</ul>
<p>
Setting to blocker status since either <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/17920" title="enhancement: Reimplement IntegerLists using Polyhedron.integral_points() (needs_work)">#17920</a> or <a class="closed ticket" href="https://trac.sagemath.org/ticket/17956" title="defect: Put back stopgap for IntegerListsLex (closed: fixed)">#17956</a> should be fixed.
</p>
TicketjdemeyerSun, 15 Mar 2015 15:32:24 GMTdescription changed
https://trac.sagemath.org/ticket/17920#comment:31
https://trac.sagemath.org/ticket/17920#comment:31
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/17920?action=diff&version=31">diff</a>)
</li>
</ul>
TicketjdemeyerSun, 15 Mar 2015 15:35:24 GMT
https://trac.sagemath.org/ticket/17920#comment:32
https://trac.sagemath.org/ticket/17920#comment:32
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:27" title="Comment 27">tscrim</a>:
</p>
<blockquote class="citation">
<p>
The first should be <code>[[2, 1], [1, 2]]</code> since the <code>inner</code> (or <code>outer</code>) are not related to the min or max lengths.
</p>
</blockquote>
<p>
To clarify: you might be confusing with the <code>floor</code> and <code>ceiling</code> arguments of <code>IntegerListsLex</code>. Those do not have any effect on the length, but <code>inner</code>/<code>outer</code> <em>do</em> add lower/upper bounds to the length. With both the existing code as well as with my code, we have for example
</p>
<pre class="wiki">sage: Compositions(3, inner=[1,1,1]).list()
[[1, 1, 1]]
</pre>
TickettscrimSun, 15 Mar 2015 15:35:42 GMTcc changed
https://trac.sagemath.org/ticket/17920#comment:33
https://trac.sagemath.org/ticket/17920#comment:33
<ul>
<li><strong>cc</strong>
<em>nthiery</em> added
</li>
</ul>
<p>
On the ordering, from the title of the class, the output should be in lexicographical order. Moreover, since these are <code>EnumeratedSets</code>, the change in the ordering could lead to subtle changes that breaks people's code.
</p>
<p>
<code>Compositions</code> also does a similar thing with the max length and <code>outer</code>, so I agree that those should be empty. However IMO these tests should be in <code>Compositions</code>.
</p>
<p>
@vdelecroix It's mostly correct and there is a lot of code which depends on this being fast. Minimal slowdowns are okay (IMO), but significant slowdowns are unacceptable.
</p>
TicketncohenSun, 15 Mar 2015 15:42:06 GMT
https://trac.sagemath.org/ticket/17920#comment:34
https://trac.sagemath.org/ticket/17920#comment:34
<blockquote class="citation">
<p>
On the ordering, from the title of the class, the output should be in lexicographical order. Moreover, since these are <code>EnumeratedSets</code>, the change in the ordering could lead to subtle changes that breaks people's code.
</p>
</blockquote>
<p>
We can sort it before returning it I guess.
</p>
<blockquote class="citation">
<p>
@vdelecroix It's mostly correct
</p>
</blockquote>
<p>
Jeroen compiled many related bugs in the description of <a class="closed ticket" href="https://trac.sagemath.org/ticket/17548" title="defect: Partitions() is buggy (closed: duplicate)">#17548</a>.
</p>
<blockquote class="citation">
<p>
Minimal slowdowns are okay (IMO), but significant slowdowns are unacceptable.
</p>
</blockquote>
<p>
Significant slowdown can be a problem, that's for sure. If they turn out to be our only way to have a code which does not return wrong results, however, we will learn to live with them.
</p>
<p>
Nathann
</p>
TicketaschillingSun, 15 Mar 2015 15:45:22 GMT
https://trac.sagemath.org/ticket/17920#comment:35
https://trac.sagemath.org/ticket/17920#comment:35
<p>
I think it is great that Jeroen implemented this to get the correct results! Of course we do want fast code at the end.
</p>
<p>
As I mentioned on sage-devel, the order of lists of tableaux does not matter very much.
</p>
<p>
As Travis mentioned, there might be some subtle places where the order matters. One example that comes to mind is that the representations of S_n and characters are returned as matrices with rows and columns indexed by integers instead of partitions. So if the order of partitions changes, the interpretation of the results might change!
</p>
TicketjdemeyerSun, 15 Mar 2015 15:47:08 GMT
https://trac.sagemath.org/ticket/17920#comment:36
https://trac.sagemath.org/ticket/17920#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:33" title="Comment 33">tscrim</a>:
</p>
<blockquote class="citation">
<p>
On the ordering, from the title of the class, the output should be in lexicographical order.
</p>
</blockquote>
<p>
The name is now <code>IntegerLists</code> and I do provide <code>IntegerListsLex</code> for "backwards compatibility" which does sort.
</p>
<p>
Since the documentation of neither <code>Partitions</code> nor <code>Compositions</code> says anything about the order, I think it's allowed to change the order.
</p>
TicketjdemeyerSun, 15 Mar 2015 15:54:46 GMT
https://trac.sagemath.org/ticket/17920#comment:37
https://trac.sagemath.org/ticket/17920#comment:37
<p>
About the speed: if you manage to fix all existing bugs in the <code>IntegerListsLex</code> code, you can again use that implementation for <code>Compositions</code> and <code>Partitions</code>. It's probably good to have two indepdendent implementations anyway.
</p>
<p>
Even better would of course be that somebody speeds up <code>Polyhedron().integral_points()</code> which would benefit everybody using polyhedra.
</p>
TicketjdemeyerSun, 15 Mar 2015 16:56:18 GMTdescription changed
https://trac.sagemath.org/ticket/17920#comment:38
https://trac.sagemath.org/ticket/17920#comment:38
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/17920?action=diff&version=38">diff</a>)
</li>
</ul>
TicketnthieryMon, 16 Mar 2015 05:10:18 GMT
https://trac.sagemath.org/ticket/17920#comment:39
https://trac.sagemath.org/ticket/17920#comment:39
<blockquote>
<p>
Dear Jeroen,
</p>
</blockquote>
<p>
Thanks a lot for taking action! It's definitely a good thing to have a
good connection between <code></code><a class="missing wiki">IntegerListLex?</a><code></code> and <code></code>Polyhedron<code></code>, as
there is some non trivial overlap. The main differences is that
<code></code><a class="missing wiki">IntegerListLex?</a><code></code> was specifically designed for allowing for
(essentially) Constant Amortized Time lexicographic Iteration in
almost constant memory, which is an important feature.
</p>
<p>
So I can see a work path along the following lines:
</p>
<ul><li>Get this ticket in to have a robust implementation of list
</li></ul><ul><li>Completely rewrite the current <code></code><a class="missing wiki">IntegerListLex?</a><code></code> iterator to be
robust (it's definitely possible); keep the Polyhedron
implementation for testing purposes as well as for counting, ...
</li></ul><ul><li>Optimize the iterator (Cythonization, using <a class="missing wiki">ClonableIntArray?</a>, ...).
</li></ul><p>
Please do not change the enumeration order, at least as default: quite
some code depends on it (I agree, this should be made explicit in the
documentation). The proposed generalizations (n in a range, negative
entries) are fine since the iterator could be made to handle them.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketjdemeyerMon, 16 Mar 2015 07:30:57 GMT
https://trac.sagemath.org/ticket/17920#comment:40
https://trac.sagemath.org/ticket/17920#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:39" title="Comment 39">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Please do not change the enumeration order, at least as default
</p>
</blockquote>
<p>
I disagree with this: the default should be "do not sort, return stuff in the fastest possible way". Sorting an iterator is very expensive and should only be done if really needed.
</p>
<blockquote class="citation">
<p>
quite some code depends on it
</p>
</blockquote>
<p>
Is that really true? The only doctest failures that I saw where "obvious" failures where some list order changed, I didn't see anything subtle.
</p>
TicketjdemeyerMon, 16 Mar 2015 08:55:49 GMT
https://trac.sagemath.org/ticket/17920#comment:41
https://trac.sagemath.org/ticket/17920#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:39" title="Comment 39">nthiery</a>:
</p>
<blockquote class="citation">
<p>
keep the Polyhedron implementation for testing purposes as well as for counting, ...
</p>
</blockquote>
<p>
I'm not sure about the counting... I guess a well-written Cython implementation of <code>IntegerListsLex</code> will usually be faster than the current polyhedra code. Profiling shows that a lot of time is spent in just <em>constructing</em> the polyhedra (if there are not so many points, enumerating them takes a lot less time than constructing the polyhedron in the first place).
</p>
TicketncohenMon, 16 Mar 2015 09:15:59 GMT
https://trac.sagemath.org/ticket/17920#comment:42
https://trac.sagemath.org/ticket/17920#comment:42
<p>
Hello,
</p>
<blockquote class="citation">
<p>
I'm not sure about the counting... I guess a well-written Cython implementation of <code>IntegerListsLex</code> will usually be faster than the current polyhedra code.
</p>
</blockquote>
<p>
True. This being said, your polyhedron code may very well be 'all we can do' to implement this feature while handling all possible combinations of parameters.
</p>
<blockquote class="citation">
<p>
Profiling shows that a lot of time is spent in just <em>constructing</em> the polyhedra
</p>
</blockquote>
<p>
True. Do you have any idea where that comes from ? I had similar troubles with the Poset constructor (related to memory usage).
</p>
<p>
Nathann
</p>
TicketjdemeyerMon, 16 Mar 2015 09:22:04 GMT
https://trac.sagemath.org/ticket/17920#comment:43
https://trac.sagemath.org/ticket/17920#comment:43
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:42" title="Comment 42">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Profiling shows that a lot of time is spent in just <em>constructing</em> the polyhedra
</p>
</blockquote>
<p>
True. Do you have any idea where that comes from ?
</p>
</blockquote>
<p>
It's just PPL.
</p>
<p>
Interestingly, arithmetic with infinity also shows up quite high in the profiling reports (up to 10% of the time), so optimizing <code>src/sage/rings/infinity.py</code> will also give some speedup.
</p>
TicketncohenMon, 16 Mar 2015 09:25:25 GMT
https://trac.sagemath.org/ticket/17920#comment:44
https://trac.sagemath.org/ticket/17920#comment:44
<blockquote class="citation">
<p>
Interestingly, arithmetic with infinity also shows up quite high in the profiling reports (up to 10% of the time), so optimizing <code>src/sage/rings/infinity.py</code> will also give some speedup.
</p>
</blockquote>
<p>
Aahahah. Yaeh, Vincent has been fighting a lot with some abstractions we have, which makes code run *much* slower. For <code>+oo</code> he advises to solve the problem by using float("inf") instead of Infinity. It is *MUCH* faster.
</p>
<p>
At some point he got some crazy somewhere by adding 'from math import sqrt' in a module to overwrite Sage's sqrt function.
</p>
<p>
Nathann
</p>
TicketjdemeyerMon, 16 Mar 2015 09:29:21 GMT
https://trac.sagemath.org/ticket/17920#comment:45
https://trac.sagemath.org/ticket/17920#comment:45
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:44" title="Comment 44">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Interestingly, arithmetic with infinity also shows up quite high in the profiling reports (up to 10% of the time), so optimizing <code>src/sage/rings/infinity.py</code> will also give some speedup.
</p>
</blockquote>
<p>
Aahahah. Yaeh, Vincent has been fighting a lot with some abstractions we have, which makes code run *much* slower. For <code>+oo</code> he advises to solve the problem by using float("inf") instead of Infinity.
</p>
</blockquote>
<p>
In general, I don't like the "X is slow, therefore let's not use X" mentality. My idea is: "let's use X and then optimize X".
</p>
TicketmmezzarobbaMon, 16 Mar 2015 10:08:16 GMT
https://trac.sagemath.org/ticket/17920#comment:46
https://trac.sagemath.org/ticket/17920#comment:46
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:45" title="Comment 45">jdemeyer</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote class="citation">
<p>
Interestingly, arithmetic with infinity also shows up quite high in the profiling reports (up to 10% of the time), so optimizing <code>src/sage/rings/infinity.py</code> will also give some speedup.
</p>
</blockquote>
<p>
Aahahah. Yaeh, Vincent has been fighting a lot with some abstractions we have, which makes code run *much* slower. For <code>+oo</code> he advises to solve the problem by using float("inf") instead of Infinity.
</p>
</blockquote>
<p>
In general, I don't like the "X is slow, therefore let's not use X" mentality. My idea is: "let's use X and then optimize X".
</p>
</blockquote>
<p>
On a tangential note: if someone makes major changes to the infinity rings, please consider adding a <code>NaN</code> element to them.
</p>
TicketncohenMon, 16 Mar 2015 10:40:52 GMT
https://trac.sagemath.org/ticket/17920#comment:47
https://trac.sagemath.org/ticket/17920#comment:47
<blockquote class="citation">
<p>
In general, I don't like the "X is slow, therefore let's not use X" mentality. My idea is: "let's use X and then optimize X".
</p>
</blockquote>
<p>
Well, for the sqrt problem we were only computing on floats, and sqrt(5) in Sage is not a float. Having this symbolic value in the code we compared it with floats and this had a cost we had no reason to pay, so <code>from math import sqrt</code> made total sense, and there was nothing in Sage's sqrt that we could have wanted to change.
</p>
<p>
As per Sage's Infinity... Well, it also seems to have been designed with a different aim in mind. I usually want speed, and I do not want to pay for pointless abstraction. In infinity.py you will find parents, elements, rings and generators, while the feature I need is already provided by the constant LONG_MAX.
</p>
<p>
This Sage object is called 'infinity', but it turns out that one definition of "infinity" cannot cover all uses that we have for infinity on a computer. And I don't think that we could beat a single CPU instruction while dealing with parents and elements in a .py file.
</p>
<p>
Nathann
</p>
TicketjdemeyerMon, 16 Mar 2015 11:50:36 GMT
https://trac.sagemath.org/ticket/17920#comment:48
https://trac.sagemath.org/ticket/17920#comment:48
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:47" title="Comment 47">ncohen</a>:
</p>
<blockquote class="citation">
<p>
while the feature I need is already provided by the constant LONG_MAX.
</p>
</blockquote>
<p>
In this case, we shouldn't aritificially restrict to <code>long</code>s:
</p>
<pre class="wiki">sage: IntegerLists(10^100, max_length=1).list()
[[10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]]
</pre><blockquote class="citation">
<p>
This Sage object is called 'infinity', but it turns out that one definition of "infinity" cannot cover all uses that we have for infinity on a computer.
</p>
</blockquote>
<p>
I think we can have one definition which covers all uses <em>within Sage</em>. There is nothing fundamentally wrong with <code>Infinity</code>, it's just slow.
</p>
TicketjdemeyerMon, 16 Mar 2015 11:54:21 GMT
https://trac.sagemath.org/ticket/17920#comment:49
https://trac.sagemath.org/ticket/17920#comment:49
<p>
Note the difference of a factor 20 between the following:
</p>
<pre class="wiki">sage: b = ZZ(1); a = Infinity; timeit('a < b', repeat=20, number=10^4)
10000 loops, best of 20: 11.7 µs per loop
sage: b = ZZ(1); a = QQ(2); timeit('a < b', repeat=20, number=10^4)
10000 loops, best of 20: 681 ns per loop
</pre><p>
A proper Cython implementation of <code>Infinity</code> should match the speed for <code>QQ</code>.
</p>
TicketgitMon, 16 Mar 2015 13:53:16 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:50
https://trac.sagemath.org/ticket/17920#comment:50
<ul>
<li><strong>commit</strong>
changed from <em>b0a04aa5a4454766ed9802d8e99abcd7fb3e105b</em> to <em>5f81a0a08bed2dc5c73f8f99dd32deafdfb3c9a1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5f81a0a08bed2dc5c73f8f99dd32deafdfb3c9a1"><span class="icon"></span>5f81a0a</a></td><td><code>Move doctests</code>
</td></tr></table>
TicketjdemeyerMon, 16 Mar 2015 13:54:04 GMT
https://trac.sagemath.org/ticket/17920#comment:51
https://trac.sagemath.org/ticket/17920#comment:51
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:33" title="Comment 33">tscrim</a>:
</p>
<blockquote class="citation">
<p>
However IMO these tests should be in <code>Compositions</code>.
</p>
</blockquote>
<p>
Done
</p>
TicketaschillingMon, 16 Mar 2015 14:29:27 GMT
https://trac.sagemath.org/ticket/17920#comment:52
https://trac.sagemath.org/ticket/17920#comment:52TicketnthieryMon, 16 Mar 2015 14:30:08 GMT
https://trac.sagemath.org/ticket/17920#comment:53
https://trac.sagemath.org/ticket/17920#comment:53
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:40" title="Comment 40">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:39" title="Comment 39">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Please do not change the enumeration order, at least as default
</p>
</blockquote>
<p>
I disagree with this: the default should be "do not sort, return stuff in the fastest possible way". Sorting an iterator is very expensive and should only be done if really needed.
</p>
</blockquote>
<p>
For <a class="missing wiki">IntegerList?</a> itself, any default is fine, and sorting is certainly
very bad. But for Partitions, Compositions, ... users are really
expecting lexicographic order. Besides, this is only a temporary
solution, and we will switch back to lexicographic once we have a
proper implementation of <a class="missing wiki">IntegerListLex?</a>.
</p>
<blockquote class="citation">
<p>
Is that really true? The only doctest failures that I saw where
"obvious" failures where some list order changed, I didn't see
anything subtle.
</p>
</blockquote>
<p>
That's a point indeed; my feeling is that we have been lucky, although
it could be that some changes w.r.t. MuPAD-Combinat makes the code
less dependent on that feature. I am worried by user's personal code
out there. Well, if you are willing to help those guys ...
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryMon, 16 Mar 2015 14:36:42 GMT
https://trac.sagemath.org/ticket/17920#comment:54
https://trac.sagemath.org/ticket/17920#comment:54
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:41" title="Comment 41">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I'm not sure about the counting... I guess a well-written Cython
implementation of <code>IntegerListsLex</code> will usually be faster than the
current polyhedra code. Profiling shows that a lot of time is spent in
just <em>constructing</em> the polyhedra (if there are not so many points,
enumerating them takes a lot less time than constructing the
polyhedron in the first place).
</p>
</blockquote>
<p>
Agreed, especially if we further go parallel: counting through
polyhedral methods only becomes relevant for relatively large
polyhedron. But this would be a very useful feature. So count
would eventually have some threshold to choose between the
two methods.
</p>
<p>
By the way: we don't yet use Barvinok-like algorithms for counting
(e.g. through LattE), or do we? This could make a difference too.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketjdemeyerMon, 16 Mar 2015 14:47:38 GMT
https://trac.sagemath.org/ticket/17920#comment:55
https://trac.sagemath.org/ticket/17920#comment:55
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:54" title="Comment 54">nthiery</a>:
</p>
<blockquote class="citation">
<p>
By the way: we don't yet use Barvinok-like algorithms for counting
(e.g. through LattE), or do we? This could make a difference too.
</p>
</blockquote>
<p>
I just read the first paragraph of the LattE manual and it does <strong>exactly</strong> what we need for counting:
</p>
<pre class="wiki">1.1 What is LattE?
The name “LattE” is an abbreviation for “Lattice point Enumeration.” LattE
was developed in 2001 to count lattice points contained in convex polyhedra
defined by linear equations and inequalities with integer coefficients. The poly-
hedra can be of any (reasonably small) dimension.
</pre>
TicketjdemeyerMon, 16 Mar 2015 14:55:34 GMT
https://trac.sagemath.org/ticket/17920#comment:56
https://trac.sagemath.org/ticket/17920#comment:56
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:53" title="Comment 53">nthiery</a>:
</p>
<blockquote class="citation">
<p>
But for Partitions, Compositions, ... users are really expecting lexicographic order.
</p>
</blockquote>
<p>
Well, certainly for <code>Compositions</code>, the current order is not defined:
</p>
<pre class="wiki">sage: Compositions(2).list()
[[1, 1], [2]]
sage: Compositions(2, max_slope=0).list()
[[2], [1, 1]]
</pre>
TicketncohenMon, 16 Mar 2015 14:56:44 GMT
https://trac.sagemath.org/ticket/17920#comment:57
https://trac.sagemath.org/ticket/17920#comment:57
<p>
<a class="ext-link" href="http://trac.sagemath.org/ticket/17529#comment:11"><span class="icon"></span>http://trac.sagemath.org/ticket/17529#comment:11</a> (we already have a LattE package)
</p>
TicketnthieryMon, 16 Mar 2015 14:58:22 GMT
https://trac.sagemath.org/ticket/17920#comment:58
https://trac.sagemath.org/ticket/17920#comment:58
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:55" title="Comment 55">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I just read the first paragraph of the LattE manual and it does <strong>exactly</strong> what we need for counting:
</p>
</blockquote>
<p>
Yes indeed! See also <a class="closed ticket" href="https://trac.sagemath.org/ticket/15180" title="enhancement: create experimental package LattE Integrale (closed: fixed)">#15180</a>.
</p>
<p>
Btw: in case this could be useful, the developers are in Davis where I
currently am for the upcoming Sage Days 64.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketgitMon, 16 Mar 2015 14:58:45 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:59
https://trac.sagemath.org/ticket/17920#comment:59
<ul>
<li><strong>commit</strong>
changed from <em>5f81a0a08bed2dc5c73f8f99dd32deafdfb3c9a1</em> to <em>6f3164941f2565627afc1128ace01973c788f767</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6f3164941f2565627afc1128ace01973c788f767"><span class="icon"></span>6f31649</a></td><td><code>Add two extra tests</code>
</td></tr></table>
TickettscrimMon, 16 Mar 2015 15:09:21 GMT
https://trac.sagemath.org/ticket/17920#comment:60
https://trac.sagemath.org/ticket/17920#comment:60
<p>
FYI - <code>float('inf')</code> works quite well as a good and fast substitute for <code>Infinity</code> (which is why it is used in the current <code>IntegerListsLex</code>).
</p>
TicketjdemeyerMon, 16 Mar 2015 15:13:34 GMT
https://trac.sagemath.org/ticket/17920#comment:61
https://trac.sagemath.org/ticket/17920#comment:61
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:53" title="Comment 53">nthiery</a>:
</p>
<blockquote class="citation">
<p>
But for Partitions users are really expecting lexicographic order.
</p>
</blockquote>
<p>
For which applications does this really matter?
</p>
<p>
I know that's how partitions are traditionally written down and how things are done in Sage historically. But I don't think that's enough reason to not change it, especially given the fact that the documentation doesn't say anything about the order. Any order of the list of partitions is a good answer mathematically.
</p>
TickettscrimMon, 16 Mar 2015 15:17:12 GMT
https://trac.sagemath.org/ticket/17920#comment:62
https://trac.sagemath.org/ticket/17920#comment:62
<p>
I'm worried this could lead to errors being raised when trying to convert between different bases of the symmetric functions (which are indexed by partitions). IIRC the code relies on some of the (graded) transition matrices being upper triangular, which requires the order be compatible with dominance ordering.
</p>
TicketjdemeyerMon, 16 Mar 2015 15:26:41 GMT
https://trac.sagemath.org/ticket/17920#comment:63
https://trac.sagemath.org/ticket/17920#comment:63
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:62" title="Comment 62">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I'm worried this could lead to errors being raised when trying to convert between different bases of the symmetric functions (which are indexed by partitions). IIRC the code relies on some of the (graded) transition matrices being upper triangular, which requires the order be compatible with dominance ordering.
</p>
</blockquote>
<p>
To be honest, I don't know what you mean mathematically. But, like I said, the fact that there are no strange doctest failures shows that the issue cannot be so serious.
</p>
<p>
And in the cases where the order really matters, I think those places should simply explicitly sort or use <code>IntegerListsLex</code>. Slowing down all of <code>Paritions()</code> just because one or two applications require it seems stupid.
</p>
TicketaschillingMon, 16 Mar 2015 19:01:58 GMT
https://trac.sagemath.org/ticket/17920#comment:64
https://trac.sagemath.org/ticket/17920#comment:64
<blockquote class="citation">
<p>
But, like I said, the fact that there are no strange doctest failures shows that the issue cannot be so serious.
</p>
</blockquote>
<p>
This might be an issue though
</p>
<pre class="wiki">sage: S=SymmetricGroup(3)
sage: S.character_table()
[ 1 -1 1]
[ 2 0 -1]
[ 1 1 1]
sage: type(S.character_table())
<type 'sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense'>
</pre><p>
The character table should really be indexed by partitions (or conjugacy classes of S_n).
So the meaning of the matrix changes if the order of the list of partitions changes.
</p>
TicketjdemeyerMon, 16 Mar 2015 19:31:46 GMT
https://trac.sagemath.org/ticket/17920#comment:65
https://trac.sagemath.org/ticket/17920#comment:65
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:64" title="Comment 64">aschilling</a>:
</p>
<blockquote class="citation">
<p>
This might be an issue though
</p>
<pre class="wiki">sage: S=SymmetricGroup(3)
sage: S.character_table()
[ 1 -1 1]
[ 2 0 -1]
[ 1 1 1]
sage: type(S.character_table())
<type 'sage.matrix.matrix_cyclo_dense.Matrix_cyclo_dense'>
</pre><p>
The character table should really be indexed by partitions (or conjugacy classes of S_n).
So the meaning of the matrix changes if the order of the list of partitions changes.
</p>
</blockquote>
<p>
Okay, so the meaning of the matrix changes. There is nothing wrong with output <em>changing</em> as long as things stay mathematically correct and internally consistent.
</p>
TicketdimpaseWed, 18 Mar 2015 10:13:48 GMT
https://trac.sagemath.org/ticket/17920#comment:66
https://trac.sagemath.org/ticket/17920#comment:66
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:55" title="Comment 55">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:54" title="Comment 54">nthiery</a>:
</p>
<blockquote class="citation">
<p>
By the way: we don't yet use Barvinok-like algorithms for counting
(e.g. through LattE), or do we? This could make a difference too.
</p>
</blockquote>
<p>
I just read the first paragraph of the LattE manual and it does <strong>exactly</strong> what we need for counting:
</p>
</blockquote>
<p>
Moreover, counting the points is faster than enumerating the points; there could be exponentially many points to count, but still the number of them is only polynomial in the input size, for fixed dimension, and LattE provides a truly polynomial-time procedure for this counting.
</p>
TicketchapotonWed, 25 Mar 2015 20:01:10 GMTstatus changed
https://trac.sagemath.org/ticket/17920#comment:67
https://trac.sagemath.org/ticket/17920#comment:67
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
a badly formated doc in composition.py
</p>
<pre class="wiki"> TESTS::
+ Check that :trac:`17548` is fixed::
</pre>
TicketgitWed, 25 Mar 2015 22:34:14 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:68
https://trac.sagemath.org/ticket/17920#comment:68
<ul>
<li><strong>commit</strong>
changed from <em>6f3164941f2565627afc1128ace01973c788f767</em> to <em>62b56ba0e0fa855ab89d832755d0219bd9f6b5f5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=62b56ba0e0fa855ab89d832755d0219bd9f6b5f5"><span class="icon"></span>62b56ba</a></td><td><code>Improve IntegerLists_polyhedron; sort Partitions by default</code>
</td></tr></table>
TicketgitWed, 25 Mar 2015 22:36:40 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:69
https://trac.sagemath.org/ticket/17920#comment:69
<ul>
<li><strong>commit</strong>
changed from <em>62b56ba0e0fa855ab89d832755d0219bd9f6b5f5</em> to <em>5096e5f0fb03432307efea20493216bf713eb020</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5096e5f0fb03432307efea20493216bf713eb020"><span class="icon"></span>5096e5f</a></td><td><code>Fix documentation</code>
</td></tr></table>
TicketjdemeyerWed, 25 Mar 2015 22:37:13 GMTstatus changed
https://trac.sagemath.org/ticket/17920#comment:70
https://trac.sagemath.org/ticket/17920#comment:70
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjdemeyerSun, 05 Apr 2015 07:00:38 GMTdependencies changed
https://trac.sagemath.org/ticket/17920#comment:71
https://trac.sagemath.org/ticket/17920#comment:71
<ul>
<li><strong>dependencies</strong>
changed from <em>#17937</em> to <em>#17937, #18087</em>
</li>
</ul>
TicketgitSun, 05 Apr 2015 07:01:25 GMTcommit changed
https://trac.sagemath.org/ticket/17920#comment:72
https://trac.sagemath.org/ticket/17920#comment:72
<ul>
<li><strong>commit</strong>
changed from <em>5096e5f0fb03432307efea20493216bf713eb020</em> to <em>621d467827d8d0c6a0cb1113cb4b861cca936f41</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c9dce18385fd59755cbcced5f1804bf60b19df07"><span class="icon"></span>c9dce18</a></td><td><code>Remove sig_on() from __dealloc__</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=621d467827d8d0c6a0cb1113cb4b861cca936f41"><span class="icon"></span>621d467</a></td><td><code>Merge commit 'c9dce18385fd59755cbcced5f1804bf60b19df07' into t/17920/ticket/17920</code>
</td></tr></table>
TicketvbraunSun, 12 Apr 2015 11:24:26 GMTpriority, status changed
https://trac.sagemath.org/ticket/17920#comment:73
https://trac.sagemath.org/ticket/17920#comment:73
<ul>
<li><strong>priority</strong>
changed from <em>blocker</em> to <em>major</em>
</li>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Whats your plan with the code here? It might be useful to check. Thoughts?
</p>
TickettscrimSun, 12 Apr 2015 11:47:09 GMTstatus changed
https://trac.sagemath.org/ticket/17920#comment:74
https://trac.sagemath.org/ticket/17920#comment:74
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
This code is useful as it works in more general context than the new <code>IntegerListsLex</code> as it allows entries in <code>ZZ</code> (instead of just <code>NN</code>) and when lex ordering doesn't hit every element in finite time. Plus I like alternative algorithms for testing, and this is faster in certain cases currently as well. I just need to find some time to review this.
</p>
TicketnthierySun, 12 Apr 2015 14:54:29 GMT
https://trac.sagemath.org/ticket/17920#comment:75
https://trac.sagemath.org/ticket/17920#comment:75
<p>
Indeed, we want this code in Sage! I promised Jeroen I would rebase his code, and work on the review. This could be a good sprint for Sage Days 67. But yes this certainly is not a blocker anymore for 6.6.
</p>
TicketjdemeyerMon, 13 Apr 2015 07:09:46 GMTstatus changed
https://trac.sagemath.org/ticket/17920#comment:76
https://trac.sagemath.org/ticket/17920#comment:76
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Needs to be rebased in any case. I might also try to make it work in <em>all</em> cases of infinite iterator (currently, I still require that there are only finitely many lists of every given length).
</p>
TicketjdemeyerMon, 13 Apr 2015 07:47:19 GMT
https://trac.sagemath.org/ticket/17920#comment:77
https://trac.sagemath.org/ticket/17920#comment:77
<p>
I would actually like to redesign <code>IntegerListsLex</code> and <code>IntegerLists_polyhedron</code> such that they share code: they could be the same class but with a different implementation for <code>__iter__</code> and <code>__contains__</code>.
</p>
TicketvdelecroixMon, 13 Apr 2015 08:00:02 GMT
https://trac.sagemath.org/ticket/17920#comment:78
https://trac.sagemath.org/ticket/17920#comment:78
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:77" title="Comment 77">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I would actually like to redesign <code>IntegerListsLex</code> and <code>IntegerLists_polyhedron</code> such that they share code: they could be the same class but with a different implementation for <code>__iter__</code> and <code>__contains__</code>.
</p>
</blockquote>
<p>
+1
</p>
<p>
why not several iterators on the same class? (with a reasonable one by default in <code>__iter__</code>).
</p>
TicketjdemeyerMon, 13 Apr 2015 08:22:33 GMT
https://trac.sagemath.org/ticket/17920#comment:79
https://trac.sagemath.org/ticket/17920#comment:79
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:78" title="Comment 78">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:77" title="Comment 77">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I would actually like to redesign <code>IntegerListsLex</code> and <code>IntegerLists_polyhedron</code> such that they share code: they could be the same class but with a different implementation for <code>__iter__</code> and <code>__contains__</code>.
</p>
</blockquote>
<p>
+1
</p>
<p>
why not several iterators on the same class? (with a reasonable one by default in <code>__iter__</code>).
</p>
</blockquote>
<p>
Well, it will be something along those lines. But I haven't thought too much about the actual design.
</p>
TicketjdemeyerMon, 13 Apr 2015 08:46:54 GMT
https://trac.sagemath.org/ticket/17920#comment:80
https://trac.sagemath.org/ticket/17920#comment:80
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:75" title="Comment 75">nthiery</a>:
</p>
<blockquote class="citation">
<p>
I promised Jeroen I would rebase his code
</p>
</blockquote>
<p>
Thanks for the offer, but that will not be needed (in any case, it's just merging with <code>-X theirs</code> essentially)
</p>
TicketnthieryMon, 13 Apr 2015 11:38:40 GMT
https://trac.sagemath.org/ticket/17920#comment:81
https://trac.sagemath.org/ticket/17920#comment:81
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:79" title="Comment 79">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:78" title="Comment 78">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17920#comment:77" title="Comment 77">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
I would actually like to redesign <code>IntegerListsLex</code> and <code>IntegerLists_polyhedron</code> such that they share code: they could be the same class but with a different implementation for <code>__iter__</code> and <code>__contains__</code>.
</p>
</blockquote>
<p>
+1
</p>
<p>
why not several iterators on the same class? (with a reasonable one by default in <code>__iter__</code>).
</p>
</blockquote>
<p>
Well, it will be something along those lines. But I haven't thought too much about the actual design.
</p>
</blockquote>
<p>
+1 to sharing code between the classes; in fact I had put a mental
note on doing this when I offered to do the merge :-)
</p>
<p>
Having a class that can handle any set of constraints, even if it does
only containment check, would be useful. We would need this in
particular to properly refactor integer vectors.
</p>
<p>
I am not sure whether we want a single class, or two classes:
</p>
<pre class="wiki">class IntegerLists:
__iter__ -> __iter__ on the polyhedron
class IntegerListsLex(IntegerLists):
</pre><p>
With the second one having the additional specification that the
enumeration shall be lexicographic.
</p>
<p>
Thoughts?
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
Ticket