Reimplement IntegerLists using Polyhedron.integral_points()

[jdemeyer]

This fixes #17548.

It also adds new features to IntegerLists:

1. Negative integers are allowed (but the default still is min_part=0).

2. There does not need to be a fixed sum, one can do for example IntegerLists(max_part=2) for all lists of integers <= 2. One can also give a lower/upper bound for the sum.

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.

Depends on #17937 Depends on #18087

CC: @nathanncohen @anneschilling @tscrim @nthiery

Component: combinatorics

Author: Jeroen Demeyer

Branch/Commit: u/jdemeyer/ticket/17920 @ 621d467

Issue created by migration from https://trac.sagemath.org/ticket/17920

[jdemeyer]

comment:2

The Sage MILP solvers cannot enumerate all solutions => closing as invalid.

[jdemeyer]

Branch: u/jdemeyer/ticket/17920

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Commit: 492696f

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

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 O_o

Nathann

---

New commits:

492696f

Reimplement IntegerLists using Polyhedron.integral_points()

[jdemeyer]

comment:6

Yes, that's what I did. Anyway, this is still very much work in progress...

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

Yes, that's what I did. Anyway, this is still very much work in progress...

Oh, okay!

Nathann

[jdemeyer]

Dependencies: #17937

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

eb6ba85	Fix integral_points() for polyhedra in 0 dimensions
5896b11	Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 492696f to 5896b11

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c835117

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5896b11 to c835117

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

755b67a

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c835117 to 755b67a

[jdemeyer]

comment:12

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 #17548.

Due to the polyhedra overhead, it is generally (a lot) slower than the existing code.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:13

Replying to @jdemeyer:

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 #17548.

Due to the polyhedra overhead, it is generally (a lot) slower than the existing code.

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.

Nathann

[jdemeyer]

comment:14

My code does not yet support all (undocumented!) features of the old IntegerListsLex, so we cannot yet replace IntegerListsLex.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 755b67a to 674a518

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

674a518

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 674a518 to 4e5dbae

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4e5dbae

Reimplement IntegerLists using Polyhedron.integral_points()

[jdemeyer]

comment:17

This now implements Compositions using my new IntegerListsLex (is the lex ordering really important? I guess not, it's for sure nowhere documented). However, doing the same for Partitions leads to all kinds of breakage and I don't understand why.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c0772f8

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4e5dbae to c0772f8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c0772f8 to 631c476

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

631c476

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3b7f4cd

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 631c476 to 3b7f4cd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3b7f4cd to 936a2c7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

936a2c7

Reimplement IntegerLists using Polyhedron.integral_points()

[jdemeyer]

comment:22

Note that this changes 3 tests (just reordering the output) in src/sage/tests/book_schilling_zabrocki_kschur_primer.py

[jdemeyer]

comment:23

The code on this ticket is essentially complete, I just need to add more doctests to comply with the "coverage" policy.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c9fa1c4

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 936a2c7 to c9fa1c4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b0a04aa

Reimplement IntegerLists using Polyhedron.integral_points()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c9fa1c4 to b0a04aa

[tscrim]

comment:27

Do you have some timings?

Also, both of these are wrong:

sage: Compositions(3, max_length=2, inner=[1,1,1]).list()
[]
sage: Compositions(10, outer=[4], inner=[1,1]).list()
[]

The first should be [[2, 1], [1, 2]] since the inner (or outer) 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 [4,6], [2,8], etc.

[videlec]

comment:28

Replying to @tscrim:

Do you have some timings?

Slow is better than wrong, isn't it? ;-)

[jdemeyer]

comment:29

Replying to @tscrim:

Do you have some timings?

My code is much slower.

Also, both of these are wrong:

sage: Compositions(3, max_length=2, inner=[1,1,1]).list()
[]
sage: Compositions(10, outer=[4], inner=[1,1]).list()
[]

The first should be [[2, 1], [1, 2]]

I don't think so. The Compositions code explicitly adds the length of the inner argument as minimal length. I didn't change this.

[jdemeyer]

comment:30

Setting to blocker status since either #17920 or #17956 should be fixed.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+This fixes #17548.

[jdemeyer]

comment:32

Replying to @tscrim:

The first should be [[2, 1], [1, 2]] since the inner (or outer) are not related to the min or max lengths.

To clarify: you might be confusing with the floor and ceiling arguments of IntegerListsLex. Those do not have any effect on the length, but inner/outer do add lower/upper bounds to the length. With both the existing code as well as with my code, we have for example

sage: Compositions(3, inner=[1,1,1]).list()
[[1, 1, 1]]

[tscrim]

comment:33

On the ordering, from the title of the class, the output should be in lexicographical order. Moreover, since these are EnumeratedSets, the change in the ordering could lead to subtle changes that breaks people's code.

Compositions also does a similar thing with the max length and outer, so I agree that those should be empty. However IMO these tests should be in Compositions.

@videlec 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.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:34

On the ordering, from the title of the class, the output should be in lexicographical order. Moreover, since these are EnumeratedSets, the change in the ordering could lead to subtle changes that breaks people's code.

We can sort it before returning it I guess.

@videlec It's mostly correct

Jeroen compiled many related bugs in the description of #17548.

Minimal slowdowns are okay (IMO), but significant slowdowns are unacceptable.

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.

Nathann

[anneschilling]

comment:35

I think it is great that Jeroen implemented this to get the correct results! Of course we do want fast code at the end.

As I mentioned on sage-devel, the order of lists of tableaux does not matter very much.

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!

[jdemeyer]

comment:36

Replying to @tscrim:

On the ordering, from the title of the class, the output should be in lexicographical order.

The name is now IntegerLists and I do provide IntegerListsLex for "backwards compatibility" which does sort.

Since the documentation of neither Partitions nor Compositions says anything about the order, I think it's allowed to change the order.

[jdemeyer]

comment:37

About the speed: if you manage to fix all existing bugs in the IntegerListsLex code, you can again use that implementation for Compositions and Partitions. It's probably good to have two indepdendent implementations anyway.

Even better would of course be that somebody speeds up Polyhedron().integral_points() which would benefit everybody using polyhedra.

[jdemeyer]

Description changed:

--- 
+++ 
@@ -1 +1,9 @@
 This fixes #17548.
+
+It also adds new features to `IntegerLists`:
+
+1. Negative integers are allowed (but the default still is `min_part=0`).
+
+2. There does not need to be a fixed sum, one can do for example `IntegerLists(max_part=2)` for all lists of integers <= 2. One can also give a lower/upper bound for the sum.
+
+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.

[nthiery]

comment:39

Dear Jeroen,

Thanks a lot for taking action! It's definitely a good thing to have a good connection between IntegerListLex and Polyhedron, as there is some non trivial overlap. The main differences is that IntegerListLex was specifically designed for allowing for (essentially) Constant Amortized Time lexicographic Iteration in almost constant memory, which is an important feature.

So I can see a work path along the following lines:

• Get this ticket in to have a robust implementation of list

• Completely rewrite the current IntegerListLex iterator to be robust (it's definitely possible); keep the Polyhedron implementation for testing purposes as well as for counting, ...

• Optimize the iterator (Cythonization, using ClonableIntArray, ...).

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.

Cheers, Nicolas

[jdemeyer]

comment:40

Replying to @nthiery:

Please do not change the enumeration order, at least as default

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.

quite some code depends on it

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.

[jdemeyer]

comment:41

Replying to @nthiery:

keep the Polyhedron implementation for testing purposes as well as for counting, ...

I'm not sure about the counting... I guess a well-written Cython implementation of IntegerListsLex will usually be faster than the current polyhedra code. Profiling shows that a lot of time is spent in just constructing the polyhedra (if there are not so many points, enumerating them takes a lot less time than constructing the polyhedron in the first place).