Skip to content

a bijectionist's toolkit#35060

Merged
vbraun merged 64 commits intosagemath:developfrom
mantepse:develop
Mar 13, 2023
Merged

a bijectionist's toolkit#35060
vbraun merged 64 commits intosagemath:developfrom
mantepse:develop

Conversation

@mantepse
Copy link
Copy Markdown
Contributor

@mantepse mantepse commented Feb 10, 2023

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

  • I have made sure that the title is self-explanatory and the description concisely explains the PR.
  • I have linked an issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation accordingly.

mantepse added 30 commits October 18, 2022 14:56
@mantepse
initial commit
6d7ab9c
@mantepse
make the linter happier
6149eb2
@mantepse
remove useless assignment
9d4bfb9
@mantepse
make initialisation more efficient
6ee34e1
@mantepse
consistently name variable
1a14bcf
@mantepse
slightly improve documentation
0901ec7
@mantepse
non-copying intersection, to save memory when there are almost no res…
c39d653 
…trictions on the values of a block
@mantepse
Merge branch 'develop' of trac.sagemath.org:sage into t/33238/a_bijec…
2f0bb0e 
…tionist_s_toolkit
@mantepse
start to cache solutions
321ba43
@mantepse
finish implementation of cache
306395c
@mantepse
Merge branch 'develop' of trac.sagemath.org:sage into t/33238/a_bijec…
1a8e564 
…tionist_s_toolkit
@mantepse
add some documentation and doctests, slightly simplify code
1ac0978
@mantepse
add missing documentation in table of contents
47945ac
@mantepse
mark doctests as long, slightly simplify logic
19c3d8f
@mantepse
slightly simplify, more doctests
eca857e
@mantepse
doctest _find_counter_example
a04d146
@mantepse
doctest add_distribution_constraints and add_intertwing_relation_cons…
3508426 
…traints
@mantepse
doctest _preprocess_intertwining_relations, _solution, _show_bmilp, _…
0ac618c 
…initialize_new_bmilp, _veto_current_solution
@mantepse
expand docstring of main class
d50b62c
@mantepse
copy milp instead of adding and removing constraints
288e391
@mantepse
derandomize a test, mark example as random
d57c8e5
@mantepse
correct typo, remove useless assignment
7353fb5
@mantepse
add and remove constraints instead of copying the whole program
db850f0
@mantepse
fix problem with SCIP, add timings
ec3271c
@mantepse
use convert for MixedIntegerLinearProgram.get_values
dfdc6ba
@mantepse
include information on MILP also in public documentation
d0836cb
@mantepse
remove unnecessary copy
563af98
@mantepse
add possibility to constrain to involutions
590bae2
@mantepse
correct indentation
da0655b
@mantepse
better handling of empty constraints
03b1fb8
tscrim
tscrim approved these changes Feb 14, 2023
View reviewed changes
Copy link
Copy Markdown
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks. LGTM.

@tscrim tscrim closed this Feb 14, 2023
@tscrim tscrim reopened this Feb 14, 2023
@tscrim
Copy link
Copy Markdown
Collaborator

tscrim commented Feb 14, 2023

Sorry, accidentally hit the wrong button.

@mantepse
Copy link
Copy Markdown
Contributor Author

mantepse commented Feb 14, 2023

Thank you so much! This ticket means a lot to me!

@mantepse mantepse added this to the sage-10.0 milestone Feb 28, 2023
@vbraun
Copy link
Copy Markdown
Member

vbraun commented Mar 11, 2023

On 32-bit:

**********************************************************************
File "src/sage/combinat/bijectionist.py", line 1578, in sage.combinat.bijectionist.Bijectionist._forced_constant_blocks
Failed example:
    for p in bij.constant_blocks(): print(list(p))
Expected:
    [[2, 1, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [4, 2, 3, 1]]
    [[3, 2, 1], [1, 3, 2], [2, 1, 3]]
    [[2, 4, 3, 1], [3, 2, 4, 1], [2, 3, 1, 4], [1, 3, 4, 2]]
    [[1, 4, 2, 3], [3, 1, 2, 4], [4, 2, 1, 3], [4, 1, 3, 2]]
    [[1, 4, 3, 2], [3, 2, 1, 4]]
    [[2, 1, 4, 3], [4, 3, 2, 1]]
    [[2, 4, 1, 3], [3, 4, 2, 1], [4, 3, 1, 2], [3, 1, 4, 2]]
Got:
    [[1, 2, 4, 3], [4, 2, 3, 1], [1, 3, 2, 4], [2, 1, 3, 4]]
    [[2, 1, 3], [3, 2, 1], [1, 3, 2]]
    [[1, 3, 4, 2], [2, 3, 1, 4], [3, 2, 4, 1], [2, 4, 3, 1]]
    [[3, 1, 2, 4], [4, 2, 1, 3], [4, 1, 3, 2], [1, 4, 2, 3]]
    [[3, 2, 1, 4], [1, 4, 3, 2]]
    [[2, 1, 4, 3], [4, 3, 2, 1]]
    [[3, 4, 2, 1], [2, 4, 1, 3], [4, 3, 1, 2], [3, 1, 4, 2]]
**********************************************************************
File "src/sage/combinat/bijectionist.py", line 1587, in sage.combinat.bijectionist.Bijectionist._forced_constant_blocks
Failed example:
    for p in bij.constant_blocks(optimal=True): sorted(p, key=len)
Expected:
    [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]
    [[1, 3, 2],
     [2, 1, 3],
     [3, 2, 1],
     [2, 3, 4, 1],
     [1, 3, 4, 2],
     [2, 1, 3, 4],
     [1, 3, 2, 4],
     [2, 3, 1, 4],
     [1, 2, 4, 3],
     [3, 2, 4, 1],
     [2, 1, 4, 3],
     [2, 4, 3, 1],
     [4, 2, 3, 1],
     [4, 3, 2, 1],
     [1, 4, 3, 2],
     [3, 2, 1, 4]]
    [[1, 4, 2, 3],
     [4, 2, 1, 3],
     [2, 4, 1, 3],
     [4, 3, 1, 2],
     [4, 1, 3, 2],
     [3, 4, 2, 1],
     [3, 1, 2, 4],
     [3, 1, 4, 2]]
Got:
    [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]
    [[3, 2, 1],
     [1, 3, 2],
     [2, 1, 3],
     [2, 1, 4, 3],
     [1, 3, 2, 4],
     [2, 4, 3, 1],
     [1, 3, 4, 2],
     [2, 3, 1, 4],
     [3, 2, 1, 4],
     [4, 2, 3, 1],
     [1, 4, 3, 2],
     [2, 1, 3, 4],
     [1, 2, 4, 3],
     [3, 2, 4, 1],
     [4, 3, 2, 1],
     [2, 3, 4, 1]]
    [[3, 1, 2, 4],
     [4, 1, 3, 2],
     [4, 3, 1, 2],
     [1, 4, 2, 3],
     [3, 4, 2, 1],
     [4, 2, 1, 3],
     [2, 4, 1, 3],
     [3, 1, 4, 2]]
**********************************************************************
1 item had failures:
   2 of  65 in sage.combinat.bijectionist.Bijectionist._forced_constant_blocks
    [579 tests, 2 failures, 69.84 s]
----------------------------------------------------------------------
sage -t --long --random-seed=0 src/sage/combinat/bijectionist.py  # 2 doctests failed
----------------------------------------------------------------------

@mantepse
Copy link
Copy Markdown
Contributor Author

mantepse commented Mar 11, 2023

@vbraun, I hope this solved the issue, but I have no way to test on 32 bit, I am sorry about that.

@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 11, 2023

Documentation preview for this PR is ready! 🎉
Built with commit: a72bd65

tscrim
tscrim approved these changes Mar 11, 2023
View reviewed changes
Copy link
Copy Markdown
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I also think this sorting should solve the issue.

@vbraun vbraun merged commit d6c38e5 into sagemath:develop Mar 13, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@tscrim tscrim tscrim approved these changes

+1 more reviewer

@mkoeppe mkoeppe mkoeppe approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

c: combinatorics p: major / 3 t: enhancement

Projects

None yet

Milestone

sage-10.0

Development

Successfully merging this pull request may close these issues.

a bijectionist's toolkit

5 participants

@mantepse @codecov-commenter @tscrim @vbraun @mkoeppe