#10534: Generation of subsets and partitions enumerated sets
-----------------------------+----------------------------------------------
Reporter: vdelecroix | Owner: vdelecroix
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6.1
Component: combinatorics | Keywords: generation, combinatorics, set,
subset, partition
Author: vdelecroix | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
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/
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10534>
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.
