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 vdelecroix)

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 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 7 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from new to needs_review

comment:3 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:4 Changed 7 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from needs_review to needs_work

comment:5 Changed 7 years ago by vdelecroix

  • Owner changed from vdelecroix to (none)

comment:6 Changed 7 years ago by vdelecroix

  • Description modified (diff)
  • Owner changed from (none) to vdelecroix

comment:7 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:8 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:9 follow-up: Changed 7 years ago by hivert

  • Authors changed from vdelecroix to Vincent Delecroix
  • Reviewers set to Florent Hivert

Hi Vincent,

Your patch looks good except a few remarks:

  • the field Author below is for credits. You should put your real name and not your login.
  • 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.
    

At least one of those two sentences is wrong. Also they seems a little redundent. This should be fixed.

I'm sorry for not having the time to put a review patch, nor finish the review now.

comment:10 in reply to: ↑ 9 Changed 7 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.

comment:11 follow-up: Changed 7 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 7 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 XXXX 

You probably want to replace XXXX by an actual number.

Done

comment:13 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:14 Changed 6 years ago by vdelecroix

  • Description modified (diff)

Nathan, you should be more explicit when asking for more info...

Note: See TracTickets for help on using tickets.