#10534: Generation of subwords, subsets and set partitions
-----------------------------+----------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.7
Component: combinatorics | Keywords: generation, combinatorics, set,
subset, partition
Author: vdelecroix | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Description changed by vdelecroix:
Old description:
> This ticket stands for a faster implementation of subset and partition
> generation of (finite or infinite) enumerated sets.
>
> The timing for anything related to Sage sage.combinat.Subwords,
> sage.combinat.Subsets, sage.combinat.SetPartitions, ... are very slow.
> The roadmap is as follows
>
> 1) '''Low level generation:''' Implement a small python extension which
> must be as performant as itertools is
>
> {{{
> sage: import itertools
> sage: list(itertools.combinations(['a','b','c'],2))
> [('a', 'b'), ('a', 'c'), ('b', 'c')]
> }}}
>
> The following will be available:
>
> * subset of given size
> * all subsets
> * set partitions with given integer combination
> * all set partitions
>
> And for each of them different order of generation (lex, revlex, Gray
> codes, ...) and output as list or tuple.
>
> Any Suggested names for iterators?
>
> combinations_lex_as_list, combinations_lex_as_tuple
> combinations_revlex_as_
>
> 2) '''Include and interface it with Sage:''' this won't be hard.
>
> REFERENCES:
>
> * Knuth TAOCP fascicule 3a
> * Python C API http://docs.python.org/c-api/
New description:
This ticket stands for a faster method of exhaustive generation of
* subwords
* subsets
* set partitions
Moreover we correct bugs and typos (see details in the patch) and create
some random generation capabilities.
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
}}}
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.47 s per loop
sage: timeit('for p in S._fast_iterator(): pass')
5 loops, best of 3: 94.1 ms per loop
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10534#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
