a bijectionist's toolkit #33238

mantepse · 2022-01-28T10:16:02Z

We provide a toolkit for the combinatorialist to help find functions ("statistics") s: A -> Z and bijections A -> B given sequences of finite sets A and B that satisfy various constraints.

Depends on #34881
Depends on #34878

CC: @stumpc5 @tscrim @fchapoton

Component: combinatorics

Author: Alexander Grosz, Tobias Kietreiber, Stephan Pfannerer, Martin Rubey

Branch/Commit: u/mantepse/a_bijectionist_s_toolkit @ 53506aa

Reviewer: Matthias Koeppe, ...

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

The text was updated successfully, but these errors were encountered:

mantepse · 2022-10-18T12:56:26Z

Branch: u/mantepse/a_bijectionist_s_toolkit

mantepse · 2022-10-18T13:04:06Z

comment:4

Comments welcome! In particular, it would be wonderful to find more interesting applications.

In short: given two finite sets A and B, a statistic tau: B -> Z, and a set partition P of A, the program finds all possible statistics s: A -> Z which have the same distribution as tau but are constant on the blocks of P.

There is still some ongoing work. In particular, we try to implement a cache of solutions, which is checked for counterexamples before asking the solver to produce a counterexample from scratch.

New commits:

`6d7ab9c`	`initial commit`

mantepse · 2022-10-18T13:04:06Z

Commit: 6d7ab9c

sagetrac-git · 2022-10-18T13:23:57Z

Changed commit from 6d7ab9c to 6149eb2

sagetrac-git · 2022-10-18T13:23:57Z

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

`6149eb2`	`make the linter happier`

sagetrac-git · 2022-10-18T16:10:17Z

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

`9d4bfb9`	`remove useless assignment`

sagetrac-git · 2022-10-18T16:10:17Z

Changed commit from 6149eb2 to 9d4bfb9

sagetrac-git · 2022-10-18T22:37:08Z

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

`6ee34e1`	`make initialisation more efficient`

sagetrac-git · 2022-10-18T22:37:08Z

Changed commit from 9d4bfb9 to 6ee34e1

sagetrac-git · 2022-10-18T22:50:28Z

Changed commit from 6ee34e1 to 1a14bcf

sagetrac-git · 2022-10-18T22:50:28Z

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

`1a14bcf`	`consistently name variable`

sagetrac-git · 2022-10-19T15:02:23Z

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

`0901ec7`	`slightly improve documentation`

sagetrac-git · 2022-10-19T15:02:23Z

Changed commit from 1a14bcf to 0901ec7

sagetrac-git · 2022-11-02T09:55:46Z

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

`c39d653`	`non-copying intersection, to save memory when there are almost no restrictions on the values of a block`

sagetrac-git · 2022-11-02T09:55:46Z

Changed commit from 0901ec7 to c39d653

sagetrac-git · 2022-12-05T08:16:49Z

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

`2f0bb0e`	`Merge branch 'develop' of trac.sagemath.org:sage into t/33238/a_bijectionist_s_toolkit`

sagetrac-git · 2022-12-05T08:16:49Z

Changed commit from c39d653 to 2f0bb0e

sagetrac-git · 2022-12-05T08:41:55Z

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

`321ba43`	`start to cache solutions`

sagetrac-git · 2022-12-05T08:41:55Z

Changed commit from 2f0bb0e to 321ba43

sagetrac-git · 2022-12-21T15:10:01Z

Changed commit from 321ba43 to 306395c

sagetrac-git · 2022-12-21T15:10:01Z

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

`306395c`	`finish implementation of cache`

mantepse · 2023-01-03T21:17:58Z

comment:122

Replying to Matthias Köppe:

Replying to Martin Rubey:

The most interesting methods is probably minimal_subdistributions_iterator

Do you have a computationally nontrivial example of using this one?

It is not so interesting anymore, since the problem has been solved, but you could look at the "benchmark example" for larger N, perhaps 7 or 8 (with minimal_subdistributions_blocks_iterator). For N=6 the output is just 18 lines, and takes about 40 seconds on my laptop. In this case, just 104 solutions of the original problem are generated (and almost all the computation goes into the milp set up in line 2075).

sagetrac-git · 2023-01-04T00:17:58Z

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

`61e97bc`	`merge _solve, solution and __iter__`

sagetrac-git · 2023-01-04T00:17:58Z

Changed commit from 6868261 to 61e97bc

mkoeppe · 2023-01-04T00:23:17Z

comment:124

Nice!

mkoeppe · 2023-01-04T00:24:26Z

comment:125

+                    # moving this out of the try...finally block breaks SCIP
+                    solution = self.milp.get_values(self._x,
+                                                    convert=bool, tolerance=0.1)

Does get_values throw an error?

mantepse · 2023-01-04T00:30:47Z

comment:126

Yes, Warning: method cannot be called before problem is solved.

(and I agree that it is better - it took me just 3 hours)

mkoeppe · 2023-01-04T00:32:22Z

comment:127

The finally block removes the transformed problem -- it's fair that it forgets the solution

mkoeppe · 2023-01-04T00:35:27Z

comment:128

Now that you have the clean interface solutions_iterator, you can write an alternative implementation using polyhedral vertex enumeration

mantepse · 2023-01-04T00:37:45Z

comment:129

Yes. Removing the other stuff, i.e.,

                    b = self.milp.get_backend()
                    if hasattr(b, "_get_model"):
                        m = b._get_model()
                        if m.getStatus() != 'unknown':
                            m.freeTransform()

gives me

        self.milp.remove_constraints(new_indices)
      File "sage/numerical/mip.pyx", line 2382, in sage.numerical.mip.MixedIntegerLinearProgram.remove_constraints
        self._backend.remove_constraints(constraints)
      File "sage/numerical/backends/generic_backend.pyx", line 432, in sage.numerical.backends.generic_backend.GenericBackend.remove_constraints
        self.remove_constraint(c)
      File "sage/numerical/backends/scip_backend.pyx", line 360, in sage.numerical.backends.scip_backend.SCIPBackend.remove_constraint
        raise ValueError("The constraint's index i must satisfy 0 <= i < number_of_constraints")
    ValueError: The constraint's index i must satisfy 0 <= i < number_of_constraints

mantepse · 2023-01-04T00:40:41Z

comment:130

Replying to Matthias Köppe:

Now that you have the clean interface solutions_iterator, you can write an alternative implementation using polyhedral vertex enumeration

I must not do this before somebody uses the tool, or I have completed my other duties. My fantasy was to finish this ticket before Christmas (last year :-)

But I am very grateful for your feedback and time!

mkoeppe · 2023-01-04T00:59:51Z

comment:131

Replying to Martin Rubey:

Yes. Removing the other stuff, i.e.,

                    b = self.milp.get_backend()
                    if hasattr(b, "_get_model"):
                        m = b._get_model()
                        if m.getStatus() != 'unknown':
                            m.freeTransform()

gives me

        self.milp.remove_constraints(new_indices)
      File "sage/numerical/mip.pyx", line 2382, in sage.numerical.mip.MixedIntegerLinearProgram.remove_constraints
        self._backend.remove_constraints(constraints)
      File "sage/numerical/backends/generic_backend.pyx", line 432, in sage.numerical.backends.generic_backend.GenericBackend.remove_constraints
        self.remove_constraint(c)
      File "sage/numerical/backends/scip_backend.pyx", line 360, in sage.numerical.backends.scip_backend.SCIPBackend.remove_constraint
        raise ValueError("The constraint's index i must satisfy 0 <= i < number_of_constraints")
    ValueError: The constraint's index i must satisfy 0 <= i < number_of_constraints

Not exactly sure what's happening there, but try if it's still necessary if you merge the (just updated) #34890

mantepse · 2023-01-04T01:39:13Z

comment:132

No, this gives me several errors. For example:

File "src/sage/combinat/bijectionist.py", line 1149, in sage.combinat.bijectionist.Bijectionist.set_distributions
Failed example:
    bij.constant_blocks(optimal=True)
Exception raised:
    Traceback (most recent call last):
      File "/home/martin/sage-develop/src/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/martin/sage-develop/src/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.bijectionist.Bijectionist.set_distributions[6]>", line 1, in <module>
        bij.constant_blocks(optimal=True)
      File "/home/martin/sage-develop/src/sage/combinat/bijectionist.py", line 647, in constant_blocks
        self._forced_constant_blocks()
      File "/home/martin/sage-develop/src/sage/combinat/bijectionist.py", line 1705, in _forced_constant_blocks
        updated_multiple_preimages[tZ + (solution[p],)].append(p)
    KeyError: [1, 3, 2]
**********************************************************************
File "src/sage/combinat/bijectionist.py", line 1151, in sage.combinat.bijectionist.Bijectionist.set_distributions
Failed example:
    sorted(bij.minimal_subdistributions_blocks_iterator(), key=lambda d: (len(d[0]), d[0]))
Exception raised:
    Traceback (most recent call last):
      File "/home/martin/sage-develop/src/sage/doctest/forker.py", line 695, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/martin/sage-develop/src/sage/doctest/forker.py", line 1093, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.bijectionist.Bijectionist.set_distributions[7]>", line 1, in <module>
        sorted(bij.minimal_subdistributions_blocks_iterator(), key=lambda d: (len(d[Integer(0)]), d[Integer(0)]))
      File "/home/martin/sage-develop/src/sage/combinat/bijectionist.py", line 2120, in minimal_subdistributions_blocks_iterator
        add_counter_example_constraint(s)
      File "/home/martin/sage-develop/src/sage/combinat/bijectionist.py", line 2093, in add_counter_example_constraint
        minimal_subdistribution.add_constraint(sum(D[p] for p in P
      File "/home/martin/sage-develop/src/sage/combinat/bijectionist.py", line 2094, in <genexpr>
        if s[p] == v) == V[v])
    KeyError: [1, 2, 3]

I have to stop now, it's 2:30am.

mkoeppe · 2023-01-04T03:51:59Z

Reviewer: Matthias Koeppe, ...

mkoeppe · 2023-01-04T18:12:16Z

comment:134

This is now OK from my side, but I've really only looked at the code from the viewpoint of managing the MIPs and getting solutions out of them. So it would be good if other reviewers could take a look on the combinatorial statistics side of things.

The code-style police will say that

+        evaluate = lambda f: sum(coeff if index == -1 else
+                                 coeff * values[index_block_value_dict[index]]
+                                 for index, coeff in f.dict().items())

should be a nested def instead.

Since the linter is currently broken, I'd recommend to run ./sage -tox -- src/sage/combinat/bijectionist.py and fix any reported issues

mantepse · 2023-01-04T18:49:26Z

comment:135

Thank you! ./sage -tox -- src/sage/combinat/bijectionist.py does not emit any warnings on my machine.

On the combinatorics side, there is still the issue with the name of set_pseudo_inverse_relation, which is currently as silly as can be, but I don't know any better and did not yet receive an answer on https://mathoverflow.net/q/437261.

mkoeppe · 2023-01-04T19:19:09Z

comment:136

You can also try ./sage -tox -e pycodestyle -- src/sage/combinat/bijectionist.py

sagetrac-git · 2023-01-04T20:17:43Z

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

`db8947b`	`pycodestyle stuff`

sagetrac-git · 2023-01-04T20:17:43Z

Changed commit from 61e97bc to db8947b

mantepse · 2023-01-17T20:13:16Z

comment:138

I think it will be best to replace pseudo_inverse_relation with quadratic_relation, unless somebody comes up with a better name.

sagetrac-git · 2023-01-20T10:28:47Z

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

`9678717`	`Merge branch 'develop' of trac.sagemath.org:sage into t/33238/a_bijectionist_s_toolkit`

sagetrac-git · 2023-01-20T10:28:47Z

Changed commit from db8947b to 9678717

sagetrac-git · 2023-01-20T10:53:57Z

Changed commit from 9678717 to 53506aa

sagetrac-git · 2023-01-20T10:53:57Z

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

`53506aa`	`rename pseudo_inverse to quadratic`

We provide a toolkit for the combinatorialist to help find functions ("statistics") s: A -> Z and bijections A -> B given sequences of finite sets A and B that satisfy various constraints. Closes #33238 ### 📝 Checklist - [x] I have made sure that the title is self-explanatory and the description concisely explains the PR. - [x] I have linked an issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation accordingly. URL: #35060 Reported by: Martin Rubey Reviewer(s): Martin Rubey, Matthias Köppe, Travis Scrimshaw

mantepse added this to the sage-9.6 milestone Jan 28, 2022

mantepse added c: combinatorics labels Jan 28, 2022

mkoeppe modified the milestones: sage-9.6, sage-9.7 Apr 2, 2022

mkoeppe modified the milestones: sage-9.7, sage-9.8 Aug 31, 2022

mantepse added the s: needs info label Oct 18, 2022

mkoeppe removed this from the sage-9.8 milestone Jan 29, 2023

mantepse mentioned this issue Feb 10, 2023

a bijectionist's toolkit #35060

Merged

4 tasks

mkoeppe removed the s: needs review label Feb 10, 2023

vbraun closed this as completed in #35060 Mar 13, 2023

mkoeppe added this to the sage-10.0 milestone Mar 13, 2023

a bijectionist's toolkit #33238

a bijectionist's toolkit #33238

Comments

mantepse commented Jan 28, 2022

mantepse commented Oct 18, 2022

mantepse commented Oct 18, 2022

mantepse commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 18, 2022

sagetrac-git mannequin commented Oct 19, 2022

sagetrac-git mannequin commented Oct 19, 2022

sagetrac-git mannequin commented Nov 2, 2022

sagetrac-git mannequin commented Nov 2, 2022

sagetrac-git mannequin commented Dec 5, 2022

sagetrac-git mannequin commented Dec 5, 2022

sagetrac-git mannequin commented Dec 5, 2022

sagetrac-git mannequin commented Dec 5, 2022

sagetrac-git mannequin commented Dec 21, 2022

sagetrac-git mannequin commented Dec 21, 2022

mantepse commented Jan 3, 2023

sagetrac-git mannequin commented Jan 4, 2023

sagetrac-git mannequin commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

mantepse commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

mantepse commented Jan 4, 2023

mantepse commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

mantepse commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

mantepse commented Jan 4, 2023

mkoeppe commented Jan 4, 2023

sagetrac-git mannequin commented Jan 4, 2023

sagetrac-git mannequin commented Jan 4, 2023

mantepse commented Jan 17, 2023

sagetrac-git mannequin commented Jan 20, 2023

sagetrac-git mannequin commented Jan 20, 2023

sagetrac-git mannequin commented Jan 20, 2023

sagetrac-git mannequin commented Jan 20, 2023