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

[nathanncohen]

Commit: 492696f

[nathanncohen]

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

[nathanncohen]

comment:7

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

Oh, okay!

Nathann

[jdemeyer]

Dependencies: #17937

[sagetrac-git]

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()

[sagetrac-git]

Changed commit from 492696f to 5896b11

[sagetrac-git]

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

c835117

Reimplement IntegerLists using Polyhedron.integral_points()

[sagetrac-git]

Changed commit from 5896b11 to c835117

[sagetrac-git]

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

755b67a

Reimplement IntegerLists using Polyhedron.integral_points()

[sagetrac-git]

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.

[nathanncohen]

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.

[sagetrac-git]

Changed commit from 755b67a to 674a518

[sagetrac-git]

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

674a518

Reimplement IntegerLists using Polyhedron.integral_points()

[sagetrac-git]

Changed commit from 674a518 to 4e5dbae

[sagetrac-git]

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.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

62b56ba

Improve IntegerLists_polyhedron; sort Partitions by default

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5096e5f

Fix documentation

[sagetrac-git]

Changed commit from 62b56ba to 5096e5f

[jdemeyer]

Changed dependencies from #17937 to #17937, #18087

[sagetrac-git]

Changed commit from 5096e5f to 621d467

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c9dce18	Remove sig_on() from __dealloc__
621d467	Merge commit 'c9dce18385fd59755cbcced5f1804bf60b19df07' into t/17920/ticket/17920

[vbraun]

comment:73

Whats your plan with the code here? It might be useful to check. Thoughts?

[tscrim]

comment:74

This code is useful as it works in more general context than the new IntegerListsLex as it allows entries in ZZ (instead of just NN) 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.

[nthiery]

comment:75

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.

[jdemeyer]

comment:76

Needs to be rebased in any case. I might also try to make it work in all cases of infinite iterator (currently, I still require that there are only finitely many lists of every given length).

[jdemeyer]

comment:77

I would actually like to redesign IntegerListsLex and IntegerLists_polyhedron such that they share code: they could be the same class but with a different implementation for __iter__ and __contains__.

[videlec]

comment:78

Replying to @jdemeyer:

I would actually like to redesign IntegerListsLex and IntegerLists_polyhedron such that they share code: they could be the same class but with a different implementation for __iter__ and __contains__.

+1

why not several iterators on the same class? (with a reasonable one by default in __iter__).

[jdemeyer]

comment:79

Replying to @videlec:

Replying to @jdemeyer:

I would actually like to redesign IntegerListsLex and IntegerLists_polyhedron such that they share code: they could be the same class but with a different implementation for __iter__ and __contains__.

+1

why not several iterators on the same class? (with a reasonable one by default in __iter__).

Well, it will be something along those lines. But I haven't thought too much about the actual design.

[jdemeyer]

comment:80

Replying to @nthiery:

I promised Jeroen I would rebase his code

Thanks for the offer, but that will not be needed (in any case, it's just merging with -X theirs essentially)

[nthiery]

comment:81

Replying to @jdemeyer:

Replying to @videlec:

Replying to @jdemeyer:

I would actually like to redesign IntegerListsLex and IntegerLists_polyhedron such that they share code: they could be the same class but with a different implementation for __iter__ and __contains__.

+1

why not several iterators on the same class? (with a reasonable one by default in __iter__).

Well, it will be something along those lines. But I haven't thought too much about the actual design.

+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 :-)

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.

I am not sure whether we want a single class, or two classes:

class IntegerLists:
    __iter__ -> __iter__ on the polyhedron

class IntegerListsLex(IntegerLists):

With the second one having the additional specification that the
enumeration shall be lexicographic.

Thoughts?

Cheers,
Nicolas