Opened 11 years ago
Closed 8 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, GitHub, GitLab)  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 11 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 11 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:3 Changed 11 years ago by
 Description modified (diff)
comment:4 Changed 11 years ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
comment:5 Changed 11 years ago by
 Owner changed from vdelecroix to (none)
comment:6 Changed 11 years ago by
 Description modified (diff)
 Owner changed from (none) to vdelecroix
comment:7 Changed 11 years ago by
 Description modified (diff)
comment:8 Changed 11 years ago by
 Status changed from needs_work to needs_review
comment:9 followup: ↓ 10 Changed 11 years ago by
 Reviewers set to Florent Hivert
comment:10 in reply to: ↑ 9 Changed 11 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 11 years ago by
comment:11 followup: ↓ 12 Changed 11 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 11 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 10 years ago by
 Status changed from needs_review to needs_info
comment:14 Changed 10 years ago by
 Description modified (diff)
Nathan, you should be more explicit when asking for more info...
comment:15 Changed 10 years ago by
 Description modified (diff)
 Status changed from needs_info to needs_review
comment:16 Changed 10 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 10 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 10 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 10 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 10 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 10 years ago by
comment:21 Changed 10 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 10 years ago by
 Description modified (diff)
Apply only:
 trac_10534generation_of_subsets_and_set_partitions.3.patch
Changed 10 years ago by
comment:23 Changed 10 years ago by
new patch, to ensure 100% doctest
comment:24 followup: ↓ 25 Changed 10 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 10 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 9 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 9 years ago by
 Status changed from needs_review to needs_work
 Work issues set to does not apply
comment:28 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:29 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:30 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:31 Changed 8 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 8 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 8 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 8 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 8 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 8 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 8 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 8 years ago by
 Branch changed from u/chapoton/10534 to public/10534
 Commit changed from efd638056cb99427de29b298169299fa171184fc to 1995fca0cc79b20ffc8863e425e50c614e61a02b
comment:39 Changed 8 years ago by
 Work issues does not apply deleted
There are some doctest continuation ...
that should be replaced by ....:
comment:40 Changed 8 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 8 years ago by
 Commit changed from e858998035ee733bbb4796c47a2b9e843c67c614 to 1d73c1b243dcc5fd25ccef10af5f3edff31e9d46
comment:42 Changed 8 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 8 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 8 years ago by
 Description modified (diff)
comment:45 Changed 8 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 8 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 8 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 8 years ago by
Merge failure due to #16067
comment:49 Changed 8 years ago by
 Status changed from positive_review to needs_work
comment:50 Changed 8 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 8 years ago by
 Status changed from needs_work to positive_review
All right. The rebase was rather trivial.
comment:52 Changed 8 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 8 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 8 years ago by
 Status changed from needs_work to positive_review
comment:55 Changed 8 years ago by
 Status changed from positive_review to needs_work
Try running the testsuite...
comment:56 Changed 8 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 8 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 8 years ago by
Will you be taking care of it Vincent or do you want me to?
comment:59 in reply to: ↑ 58 Changed 8 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 8 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 8 years ago by
 Status changed from needs_work to needs_review
Hey Travis,
Please double check that everything is fine.
Vincent
comment:62 Changed 8 years ago by
 Status changed from needs_review to positive_review
LGTM. Thanks Vincent.
comment:63 Changed 8 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.