Opened 7 years ago
Closed 4 years ago
#10534 closed enhancement (fixed)
Cleanup in choose_nk, split_nk, subword, subset
Reported by:  vdelecroix  Owned by:  vdelecroix 

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  generation, combinatorics, set, subset, partition 
Cc:  sagecombinat  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 )
 deprecate
ChooseNK
(insage.combinat.choose_nk
) andSplitNK
(insage.combinat.split_nk
).  clean
sage.combinat.subword
andsage.combinat.subset
 inheritance from
Parent
 much better iteration/random generation
 ...
 inheritance from
And become more pep8 compliant ;=)
see also: #16472
Attachments (3)
Change History (66)
comment:1 Changed 7 years ago by
 Description modified (diff)
 Summary changed from Generation of subsets and partitions enumerated sets to Generation of subwords, subsets and set partitions
comment:2 Changed 7 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:3 Changed 7 years ago by
 Description modified (diff)
comment:4 Changed 7 years ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
comment:5 Changed 7 years ago by
 Owner changed from vdelecroix to (none)
comment:6 Changed 7 years ago by
 Description modified (diff)
 Owner changed from (none) to vdelecroix
comment:7 Changed 7 years ago by
 Description modified (diff)
comment:8 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:9 followup: ↓ 10 Changed 7 years ago by
 Reviewers set to Florent Hivert
comment:10 in reply to: ↑ 9 Changed 7 years ago by
 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 7 years ago by
comment:11 followup: ↓ 12 Changed 7 years ago by
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 7 years ago by
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 6 years ago by
 Status changed from needs_review to needs_info
comment:14 Changed 6 years ago by
 Description modified (diff)
Nathan, you should be more explicit when asking for more info...
comment:15 Changed 6 years ago by
 Description modified (diff)
 Status changed from needs_info to needs_review
comment:16 Changed 6 years ago by
 Summary changed from Generation of subwords, subsets and set partitions to Optimizations for the generation of subwords, subsets and set partitions
comment:17 Changed 6 years ago by
I update the file to make it works on sage5.0. I will update the corresponding patch in the combinat queue.
comment:18 Changed 6 years ago by
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 followup: ↓ 20 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
comment:21 Changed 6 years ago by
I correct the error and add the ticket number on the first line of the patch (as asked by the patchbot).
comment:22 Changed 6 years ago by
 Description modified (diff)
Apply only:
 trac_10534generation_of_subsets_and_set_partitions.3.patch
Changed 6 years ago by
comment:23 Changed 6 years ago by
new patch, to ensure 100% doctest
comment:24 followup: ↓ 25 Changed 5 years ago by
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/sagemain/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 5 years ago by
SCORE /Applications/sage/devel/sagemain/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 5 years ago by
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 5 years ago by
 Status changed from needs_review to needs_work
 Work issues set to does not apply
comment:28 Changed 5 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:29 Changed 4 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:30 Changed 4 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:31 Changed 4 years ago by
 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 followup: ↓ 34 Changed 4 years ago by
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 4 years ago by
Ok. From the commit you proposed, I think we could
 deprecate
ChooseNK
andSplitNK
as it is used nowhere and subsumed by subsets and set partitions.  do some more cleaning in
combination.py
,subset.py
andsubwords.py
: remove the inheritance from
CombinatorialClass
and make them inherit fromParent
. We would set the category toEnumeratedSets().Finite()
 better iteration
 make
Subwords
work with words as inputsage: Subwords(Word([1,2,3,4,5])) Traceback (most recent call last): ... ValueError: datatype should be str, list or tuple
 etc
 remove the inheritance from
If you agree with this, I can modify the ticket description and propose a commit.
Vincent
comment:34 in reply to: ↑ 32 Changed 4 years ago by
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 4 years ago by
 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 4 years ago by
I have made a cleanup 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 cleanup commit..
comment:37 Changed 4 years ago by
 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 4 years ago by
 Branch changed from u/chapoton/10534 to public/10534
 Commit changed from efd638056cb99427de29b298169299fa171184fc to 1995fca0cc79b20ffc8863e425e50c614e61a02b
comment:39 Changed 4 years ago by
 Work issues does not apply deleted
There are some doctest continuation ...
that should be replaced by ....:
comment:40 Changed 4 years ago by
 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 4 years ago by
 Commit changed from e858998035ee733bbb4796c47a2b9e843c67c614 to 1d73c1b243dcc5fd25ccef10af5f3edff31e9d46
comment:42 Changed 4 years ago by
 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 4 years ago by
 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 4 years ago by
 Description modified (diff)
comment:45 Changed 4 years ago by
 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 followup: ↓ 47 Changed 4 years ago by
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 4 years ago by
 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, butSet_object_enumerated
is actually a subclass ofParent
causing layout conflicts...uggg). I've made some minor tweaks and changed the strings to the python 3format
. If you're happy with my changes, then positive review. Other things (like removingCombinatorialClass
fromCombinations
and theelement_class
thing) can be on followups.
Thanks for your contribution on this!
Vincent
comment:48 Changed 4 years ago by
Merge failure due to #16067
comment:49 Changed 4 years ago by
 Status changed from positive_review to needs_work
comment:50 Changed 4 years ago by
 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 4 years ago by
 Status changed from needs_work to positive_review
All right. The rebase was rather trivial.
comment:52 Changed 4 years ago by
 Status changed from positive_review to needs_work
sage t long src/sage/misc/sageinspect.py # 1 doctest failed
comment:53 Changed 4 years ago by
 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 4 years ago by
 Status changed from needs_work to positive_review
comment:55 Changed 4 years ago by
 Status changed from positive_review to needs_work
Try running the testsuite...
comment:56 Changed 4 years ago by
I did (again):
travis@travissage:~/sage/src/sage/misc$ sage tp sageinspect.py Running doctests with ID 201406150938197033a8ad. 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@travissage:~/sage/src/sage/misc$ sage tp long sageinspect.py Running doctests with ID 201406150940500dd08e9e. 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 4 years ago by
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 followup: ↓ 59 Changed 4 years ago by
Will you be taking care of it Vincent or do you want me to?
comment:59 in reply to: ↑ 58 Changed 4 years ago by
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 4 years ago by
 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 4 years ago by
 Status changed from needs_work to needs_review
Hey Travis,
Please double check that everything is fine.
Vincent
comment:62 Changed 4 years ago by
 Status changed from needs_review to positive_review
LGTM. Thanks Vincent.
comment:63 Changed 4 years ago by
 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.