#6812: Enumerate integer vectors modulo to the action of a Permutation Group
------------------------------------------------------------------+---------
Reporter: nborie |
Owner: nborie
Type: enhancement |
Status: needs_review
Priority: major |
Milestone: sage-5.1
Component: combinatorics |
Resolution:
Keywords: enumeration, integer, list, permutation, group | Work
issues: long time tests, information about listing infinite sets
Report Upstream: N/A |
Reviewers: Karl-Dieter Crisman, Simon King
Authors: Nicolas Borie | Merged
in:
Dependencies: #10334, #10335 |
Stopgaps:
------------------------------------------------------------------+---------
Changes (by nborie):
* status: needs_work => needs_review
Comment:
Ok, here is a last version :
- Including categories of quotient of set and (In)finite enumerated set
- Using the cython data structure based on C array
- Tests of coherences with others features from combinat (Partition,
monomials, graphs)
- Handling of 0-1 enumeration (like adjacent matrix of graph)
On this last Patch, all tests pass with --long and --optional for the two
new files. I didn't run all tests of Sage but this new feature is
orthogonal with other part of Sage. The docbuild produce no warning and
the doc looks clean.
To present one other test, here is the way to build all unlabeled graphs
over 7 vertices :
{{{
sage: G = TransitiveGroup(21,38)
sage: G.cardinality() == factorial(7)
True
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: S._cardinality_from_iterator()
1044
}}}
This module, not optimized for the graphs do that in less than 1 minutes
on my 4 years old macbook. As improvement for the future, the code is
trivially "parallelizable". But this parallelization should be done on
SearchForest and not on this module.
For the reviewer, please be careful with my English. I still try to
correct myself as much but I am sure some sentences are not full-sense and
there are probably some mistakes that flyspell (and me) didn't catch.
apply trac_6812_integer_vectors_mod_permgroup.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6812#comment:58>
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.
