Opened 7 years ago
Last modified 4 years ago
#10534 closed enhancement
Generation of subwords, subsets and set partitions — at Version 14
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 | Reviewers: | Florent Hivert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This ticket stands for a faster method of exhaustive generation of combinatorial object that may be found in sage.combinat.* and more precisely
- subwords (sage.combinat.subword)
- subsets (sage.combinat.subset)
- set partitions (sage.combinat.set_partitions and sage.combinat.set_partition_ordered)
Most of the time, the improvment just consists in calling the python library itertools. For other, it consists in creating a lower level Python iterator which does not use the heavy mechanism of Parent/Element? (which is not intended for the frontend user).
Moreover, the patch provides
- bugs and typos corrections (doctest coverage is now 100%)
- random generation capabilities
- modified cardinality method which always return a Sage Integer (and no more Python int or Sage Rational)
Some timings (on Intel(R) Core(TM)2 Duo CPU T8100 @ 2.10GHz)
Old version
sage: S = SetPartitions(8,[3,3,2]) sage: timeit('for p in S: pass') 5 loops, best of 3: 401 ms per loop sage: S = SetPartitions(9,[3,3,2,1]) sage: timeit('for p in S: pass') 5 loops, best of 3: 4 s per loop sage: S = Subsets([1]*1+[2]*2+[3]*3+[4]*4+[5]*5, submultiset=True) sage: timeit('S.cardinality()') 5 loops, best of 3: 712 ms per loop
New version
sage: S = SetPartitions(8,[3,3,2]) sage: timeit('for p in S: pass') 5 loops, best of 3: 130 ms per loop sage: timeit('for p in S._fast_iterator(): pass') 25 loops, best of 3: 10.4 ms per loop sage: S = SetPartitions(9,[3,3,2,1]) sage: timeit('for p in S: pass') 5 loops, best of 3: 1.43 s per loop sage: timeit('for p in S._fast_iterator(): pass') 5 loops, best of 3: 91.3 ms per loop sage: S = Subsets([1]*1+[2]*2+[3]*3+[4]*4+[5]*5,submultiset=True) sage: timeit('S.cardinality()') 625 loops, best of 3: 33.9 µs per loop
Change History (15)
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 follow-up: ↓ 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 follow-up: ↓ 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...
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.