Opened 8 years ago

# Generation of subwords, subsets and set partitions — at Version 14

Reported by: Owned by: vdelecroix vdelecroix major sage-6.3 combinatorics generation, combinatorics, set, subset, partition sage-combinat Vincent Delecroix Florent Hivert N/A

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
```

### comment:1 Changed 8 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 8 years ago by vdelecroix

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

### comment:3 Changed 8 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: ↓ 10 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: ↓ 12 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 7 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.