Opened 4 years ago
Closed 4 months ago
#10534 closed enhancement (fixed)
Cleanup in choose_nk, split_nk, subword, subset
Reported by: | vdelecroix | Owned by: | vdelecroix |
---|---|---|---|
Priority: | major | Milestone: | sage-6.3 |
Component: | combinatorics | Keywords: | generation, combinatorics, set, subset, partition |
Cc: | sage-combinat | Merged in: | |
Authors: | Vincent Delecroix, Frédéric Chapoton | Reviewers: | Florent Hivert, Frédéric Chapoton, Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 714f266 (Commits) | Commit: | 714f266d81f57dd6d98daa5598a3b54478c213c8 |
Dependencies: | Stopgaps: |
Description (last modified by vdelecroix)
- deprecate ChooseNK (in sage.combinat.choose_nk) and SplitNK (in sage.combinat.split_nk).
- clean sage.combinat.subword and sage.combinat.subset
- inheritance from Parent
- much better iteration/random generation
- ...
And become more pep8 compliant ;=)
see also: #16472
Attachments (3)
Change History (66)
comment:1 Changed 4 years ago by vdelecroix
- Description modified (diff)
- Summary changed from Generation of subsets and partitions enumerated sets to Generation of subwords, subsets and set partitions
comment:2 Changed 4 years ago by vdelecroix
- Description modified (diff)
- Status changed from new to needs_review
comment:3 Changed 4 years ago by vdelecroix
- Description modified (diff)
comment:4 Changed 4 years ago by vdelecroix
- Description modified (diff)
- Status changed from needs_review to needs_work
comment:5 Changed 3 years ago by vdelecroix
- Owner vdelecroix deleted
comment:6 Changed 3 years ago by vdelecroix
- Description modified (diff)
- Owner set to vdelecroix
comment:7 Changed 3 years ago by vdelecroix
- Description modified (diff)
comment:8 Changed 3 years ago by vdelecroix
- Status changed from needs_work to needs_review
comment:9 follow-up: ↓ 10 Changed 3 years ago by hivert
- Reviewers set to Florent Hivert
comment:10 in reply to: ↑ 9 Changed 3 years ago by vdelecroix
- the field Author below is for credits. You should put your real name and not your login.
Thank you for modifying this.
- the documentation now says:
[...] The elements of the output are tuples of Python int (and not Sage Integer). [...] It's element are returned as plain list of python int.
That's right. Output value are now tuples and it is fully specified.
Changed 3 years ago by vdelecroix
comment:11 follow-up: ↓ 12 Changed 3 years ago by hivert
Hi Vincent,
I need more time to review your long patch. I just notice the following:
file: sage/combinat/choose_nk.py 85 sage: [0,2] in c52 # trac XXXX
You probably want to replace XXXX by an actual number. I'll continue my review tomorrow (hopefully)
Florent
comment:12 in reply to: ↑ 11 Changed 3 years ago by vdelecroix
Hi Florent
I need more time to review your long patch.
Certainly. Thanks for the review.
I have three important design questions relative to that patch and the Combinatorial classes which it modify
- should the attributes of a CombinatorialClass? be visible like S.w or do we prefer S._w (some code in graphs uses a direct call to S.w) ?
- what should be the inheritance/relations between say Subsets (subset of a given set) and Subsets_k (subset of size k of a given set) ?
- what should be the output of Subwords ? tuple, list, strings, any user defined type ? Actually, if you initialize it with list (resp. tuple, string) it output lists (resp. tuple, string).
I just notice the following:
file: sage/combinat/choose_nk.py 85 sage: [0,2] in c52 # trac XXXXYou probably want to replace XXXX by an actual number.
Done
comment:13 Changed 3 years ago by ncohen
- Status changed from needs_review to needs_info
comment:14 Changed 3 years ago by vdelecroix
- Description modified (diff)
Nathan, you should be more explicit when asking for more info...
comment:15 Changed 3 years ago by vdelecroix
- Description modified (diff)
- Status changed from needs_info to needs_review
comment:16 Changed 2 years ago by nthiery
- Summary changed from Generation of subwords, subsets and set partitions to Optimizations for the generation of subwords, subsets and set partitions
comment:17 Changed 2 years ago by vdelecroix
I update the file to make it works on sage-5.0. I will update the corresponding patch in the combinat queue.
comment:18 Changed 2 years ago by chapoton
This code breaks a test in polytopes.parallelotope, because this last procedure calls Combinations and expect to receive a list and not a tuple. This has to be cured, maybe by inserting a list() at the appropriate place in this procedure. Please test that the correction works before uploading a new patch.
Please also remove all trailing whitespaces, see the bot report.
comment:19 follow-up: ↓ 20 Changed 2 years ago by chapoton
Here is a minimal example of what goes wrong in polytopes.parallelotope :
sage: g=[ vector([1,0]), vector([0,1])] sage: Combinations(g)
This is a mutability/hash problem, when trying to convert a multiset in a set, apparently..
comment:20 in reply to: ↑ 19 Changed 2 years ago by vdelecroix
Replying to chapoton:
Here is a minimal example of what goes wrong in polytopes.parallelotope :
sage: g=[ vector([1,0]), vector([0,1])] sage: Combinations(g)This is a mutability/hash problem, when trying to convert a multiset in a set, apparently..
In the above example, the command fails because the *vector* is not hashable.
Changed 2 years ago by vdelecroix
comment:21 Changed 2 years ago by vdelecroix
I correct the error and add the ticket number on the first line of the patch (as asked by the patchbot).
comment:22 Changed 2 years ago by chapoton
- Description modified (diff)
Apply only:
- trac_10534-generation_of_subsets_and_set_partitions.3.patch
Changed 2 years ago by chapoton
comment:23 Changed 2 years ago by chapoton
new patch, to ensure 100% doctest
comment:24 follow-up: ↓ 25 Changed 2 years ago by emchennyc
I got 100% doctest coverage for all the edited files but there was one warning. If someone doesn't mind explaining what is the significance of this, that would be helpful.
SCORE /Applications/sage/devel/sage-main/sage/combinat/subset.py: 100% (33 of 33)
Possibly wrong (function name doesn't occur in doctests):
- _element_constructor_(self, x):
- _element_constructor_(self, x):
Also, "devel/sage/sage/tests/interrupt.pyx" timed out when I ran the long doctests.
comment:25 in reply to: ↑ 24 Changed 2 years ago by vdelecroix
SCORE /Applications/sage/devel/sage-main/sage/combinat/subset.py: 100% (33 of 33)
Possibly wrong (function name doesn't occur in doctests):
- _element_constructor_(self, x):
- _element_constructor_(self, x):
This is because the methods _element_constructor_(self, x) are not directly tested. There should be a comment "# indirect doctest" after the corresponding test. Basically, this function is used to build an element of a parent, but it is called through the method call of the parent (which is implemented in Parent).
Also, "devel/sage/sage/tests/interrupt.pyx" timed out when I ran the long doctests.
This is much more ennoying and I do not know why.
comment:26 Changed 20 months ago by ncohen
Helloooooooooooooooo !!!
While I read your patch, two things :
- an "It's" should become an "its"
- why do you change the ouput type from lists to tuples ?
Btw, sorry I did not answer your comment many months ago, I may have missed the warning from trac : I had set the ticket to needs_info because you seemed to be asking rather fundamental questions which would have had an impact on the patch, so that it would have been a pity to review the patch if you intended to change it so much later.
Have you had an answer from Florent since ?
Nathann
comment:27 Changed 17 months ago by vdelecroix
- Status changed from needs_review to needs_work
- Work issues set to does not apply
comment:28 Changed 15 months ago by jdemeyer
- Milestone changed from sage-5.11 to sage-5.12
comment:29 Changed 9 months ago by vbraun_spam
- Milestone changed from sage-6.1 to sage-6.2
comment:30 Changed 6 months ago by vbraun_spam
- Milestone changed from sage-6.2 to sage-6.3
comment:31 Changed 5 months ago by chapoton
- Branch set to u/chapoton/10534
- Commit set to 8e30be38b2e924e4bc4b6a46d68a3a32a1ee7ae5
Hello,
I have made a branch from the latest patch, but only partially. I have not touched the files set_partition and set_partition_ordered.
Maybe one could just try to get this smaller changes in ?
New commits:
48cd968 | trac 10534: Optimizations for the generation of subwords, subsets and set partitions |
8e30be3 | trac #10534 partial conversion of the mercurial patch |
comment:32 follow-up: ↓ 34 Changed 5 months ago by vdelecroix
Hi,
You deserve a necromancy badge ;-) I gave up on that ticket since Travis was refactoring a lot in sage.combinat.*. It definitely makes sense to have at least a portion of it. I will have a look.
Vincent
comment:33 Changed 5 months ago by vdelecroix
Ok. From the commit you proposed, I think we could
- deprecate ChooseNK and SplitNK as it is used nowhere and subsumed by subsets and set partitions.
- do some more cleaning in combination.py, subset.py and subwords.py:
- remove the inheritance from CombinatorialClass and make them inherit from Parent. We would set the category to EnumeratedSets().Finite()
- better iteration
- make Subwords work with words as input
sage: Subwords(Word([1,2,3,4,5])) Traceback (most recent call last): ... ValueError: datatype should be str, list or tuple
- etc
If you agree with this, I can modify the ticket description and propose a commit.
Vincent
comment:34 in reply to: ↑ 32 Changed 5 months ago by tscrim
Replying to vdelecroix:
You deserve a necromancy badge ;-) I gave up on that ticket since Travis was refactoring a lot in sage.combinat.*. It definitely makes sense to have at least a portion of it. I will have a look.
I don't really have time right now to keep going through that, as much as I'd like to. +1 on getting this in. I don't remember if I had any (partial) removal of CombinatorialClass in combination.py, subset.py, or subwords.py to give as a starting point, but I don't think I did. However if you have any problems with doing this, I might have some answers so feel free to ask.
Best,
Travis
comment:35 Changed 5 months ago by git
- Commit changed from 8e30be38b2e924e4bc4b6a46d68a3a32a1ee7ae5 to efd638056cb99427de29b298169299fa171184fc
Branch pushed to git repo; I updated commit sha1. New commits:
efd6380 | trac #10534 just a partial pep8 cleanup |
comment:36 Changed 5 months ago by chapoton
I have made a clean-up commit, changin only small details such as raise syntax and so on. I will now stop working on that.
I agree with the changes that you propose. I hope there will be no merge problem with my stupid clean-up commit..
comment:37 Changed 5 months ago by vdelecroix
- Description modified (diff)
- Summary changed from Optimizations for the generation of subwords, subsets and set partitions to Cleanup in choose_nk, split_nk, subword, subset
comment:38 Changed 5 months ago by vdelecroix
- Branch changed from u/chapoton/10534 to public/10534
- Commit changed from efd638056cb99427de29b298169299fa171184fc to 1995fca0cc79b20ffc8863e425e50c614e61a02b
comment:39 Changed 5 months ago by chapoton
- Work issues does not apply deleted
There are some doctest continuation ... that should be replaced by ....:
comment:40 Changed 5 months ago by git
- Commit changed from 1995fca0cc79b20ffc8863e425e50c614e61a02b to e858998035ee733bbb4796c47a2b9e843c67c614
Branch pushed to git repo; I updated commit sha1. New commits:
e858998 | trac #10534 doctest continuation using ...: |
comment:41 Changed 5 months ago by git
- Commit changed from e858998035ee733bbb4796c47a2b9e843c67c614 to 1d73c1b243dcc5fd25ccef10af5f3edff31e9d46
comment:42 Changed 5 months ago by vdelecroix
- Status changed from needs_work to needs_review
Very cool... now we can do
sage: S = Subsets(Subsets(Subsets(3))) sage: S.cardinality() 115792089237316195423570985008687907853269984665640564039457584007913129639936 sage: S.unrank(14321093401985) {{{1, 3}, {3}}, {{2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}}, {{1, 3}, {2}, {2, 3}, {}, {3}}, {{2}}, {}, {{1, 3}, {1, 2}, {2}, {3}}, {{2}, {1}}, {{1, 2}, {2}, {1}}} sage: S.random_element() ...
(so I updated the tutorial which had before a #long time for that kind of examples). And moreover no CombinatorialClass anymore.
Needs review!
Vincent
comment:43 Changed 5 months ago by git
- Commit changed from 1d73c1b243dcc5fd25ccef10af5f3edff31e9d46 to 772615d0b343605327a8089a838c75dad798c1c2
Branch pushed to git repo; I updated commit sha1. New commits:
772615d | trac #10534 removed unused imports |
comment:44 Changed 5 months ago by vdelecroix
- Description modified (diff)
comment:45 Changed 5 months ago by git
- Commit changed from 772615d0b343605327a8089a838c75dad798c1c2 to c3979afa7d7a304abc5b8b9ba5d0e2f3c25f6984
Branch pushed to git repo; I updated commit sha1. New commits:
c3979af | Some review tweaks and python 3 stuff. |
comment:46 follow-up: ↓ 47 Changed 5 months ago by tscrim
Hey Vincent, I've gone through and it looks good (I tried to change the element_class workaround, but Set_object_enumerated is actually a subclass of Parent causing layout conflicts...uggg). I've made some minor tweaks and changed the strings to the python 3 format. If you're happy with my changes, then positive review. Other things (like removing CombinatorialClass from Combinations and the element_class thing) can be on followups.
comment:47 in reply to: ↑ 46 Changed 5 months ago by vdelecroix
- Reviewers changed from Florent Hivert to Florent Hivert, Frédéric Chapoton, Travis Scrimshaw
- Status changed from needs_review to positive_review
Replying to tscrim:
Hey Vincent, I've gone through and it looks good (I tried to change the element_class workaround, but Set_object_enumerated is actually a subclass of Parent causing layout conflicts...uggg). I've made some minor tweaks and changed the strings to the python 3 format. If you're happy with my changes, then positive review. Other things (like removing CombinatorialClass from Combinations and the element_class thing) can be on followups.
Thanks for your contribution on this!
Vincent
comment:48 Changed 5 months ago by vbraun
Merge failure due to #16067
comment:49 Changed 5 months ago by vbraun
- Status changed from positive_review to needs_work
comment:50 Changed 5 months ago by git
- Commit changed from c3979afa7d7a304abc5b8b9ba5d0e2f3c25f6984 to 9146bde20c077c880c8f364e99bb8ef4c879de41
Branch pushed to git repo; I updated commit sha1. New commits:
e574c68 | trac #16067: changes generated by "2to3 -w -f filter src/sage" |
65c8620 | trac #16067: fix an error generated by "2to3" |
1d50592 | trac #16067: tidying up the generated patch |
c68a033 | Merge branch 'develop' into u/wluebbe/ticket/16067 |
0cebea1 | Merge branch 'develop' into u/wluebbe/ticket/16067 |
0c2486e | trac #16067: answered reviewer comments and further improvements |
49e52c3 | trac #16067: fixed duplicate lines found by reviewer |
9146bde | trac #10534: merge #16067 |
comment:51 Changed 5 months ago by vdelecroix
- Status changed from needs_work to positive_review
All right. The rebase was rather trivial.
comment:52 Changed 5 months ago by vbraun
- Status changed from positive_review to needs_work
sage -t --long src/sage/misc/sageinspect.py # 1 doctest failed
comment:53 Changed 5 months ago by git
- Commit changed from 9146bde20c077c880c8f364e99bb8ef4c879de41 to d9637bdbfa0f65d670c8fbcdb8425661f36c6343
Branch pushed to git repo; I updated commit sha1. New commits:
d9637bd | Trivial doctest fix due to line number changes. |
comment:54 Changed 5 months ago by tscrim
- Status changed from needs_work to positive_review
comment:55 Changed 5 months ago by vbraun
- Status changed from positive_review to needs_work
Try running the testsuite...
comment:56 Changed 5 months ago by tscrim
I did (again):
travis@travis-sage:~/sage/src/sage/misc$ sage -tp sageinspect.py Running doctests with ID 2014-06-15-09-38-19-7033a8ad. Doctesting 1 file using 4 threads. sage -t sageinspect.py [251 tests, 24.24 s] ---------------------------------------------------------------------- All tests passed! ---------------------------------------------------------------------- Total time for all tests: 24.6 seconds cpu time: 4.7 seconds cumulative wall time: 24.2 seconds travis@travis-sage:~/sage/src/sage/misc$ sage -tp --long sageinspect.py Running doctests with ID 2014-06-15-09-40-50-0dd08e9e. Doctesting 1 file using 4 threads. sage -t --long sageinspect.py [251 tests, 24.16 s] ---------------------------------------------------------------------- All tests passed! ---------------------------------------------------------------------- Total time for all tests: 24.5 seconds cpu time: 4.7 seconds cumulative wall time: 24.2 seconds
Is there a failure elsewhere (I also checked the failures that the patchbot reported and those passed)?
comment:57 Changed 5 months ago by vdelecroix
Same problem as in #16472
sage -t --long structure/sage_object.pyx ********************************************************************** File "structure/sage_object.pyx", line 1346, in sage.structure.sage_object.unpickle_all Failed example: sage.structure.sage_object.unpickle_all() # (4s on sage.math, 2011) Expected ... Got: ... Failed: _class__sage_combinat_choose_nk_ChooseNK__.sobj _class__sage_combinat_split_nk_SplitNK_nk__.sobj
If the approach with __setstate__ is more standard then we should go for it here as well.
comment:58 follow-up: ↓ 59 Changed 5 months ago by tscrim
Will you be taking care of it Vincent or do you want me to?
comment:59 in reply to: ↑ 58 Changed 5 months ago by vdelecroix
Replying to tscrim:
Will you be taking care of it Vincent or do you want me to?
No, no. I will do it along your lines. Thanks for proposing.
comment:60 Changed 5 months ago by git
- Commit changed from d9637bdbfa0f65d670c8fbcdb8425661f36c6343 to 714f266d81f57dd6d98daa5598a3b54478c213c8
Branch pushed to git repo; I updated commit sha1. New commits:
714f266 | trac #10534: fix pickling |
comment:61 Changed 5 months ago by vdelecroix
- Status changed from needs_work to needs_review
Hey Travis,
Please double check that everything is fine.
Vincent
comment:62 Changed 5 months ago by tscrim
- Status changed from needs_review to positive_review
LGTM. Thanks Vincent.
comment:63 Changed 4 months ago by vbraun
- Branch changed from public/10534 to 714f266d81f57dd6d98daa5598a3b54478c213c8
- Resolution set to fixed
- Status changed from positive_review to closed
Hi Vincent,
Your patch looks good except a few remarks:
I'm sorry for not having the time to put a review patch, nor finish the review
now.