#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: |
Stopgaps:
------------------------------------------------------------------+---------
Comment (by nborie):
Replying to [comment:83 SimonKing]:
> But I do think that the orbit method should try to convert the input
vector from a different parent into self, and should certainly not return
"None".
Yes! None is not an option here. It must return a set or raise an error.
> Of course. The algorithm for is_canonical looks almost the same as the
full expansion of an orbit, but if it is in fact non-canonical then the
function will return "False" before finishing the computation of the whole
orbit.
And more than that, there is a king of gardener lemma inside the
is_canonical method, the partial_lex comparison cut some branches of the
orbit just by reading the first entries.
I also think the change from list to set produce more than x2 speedup, it
is probably an exponential optimization, you should try before and after
with graphs over 7 vertices :
{{{
sage: G = TransitiveGroup(21,38)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: time S._cardinality_from_iterator()
1044
Time: CPU 128.64 s, Wall: 136.10 s
}}}
It become to be a large test for this last one. (1044 symmetric matrices
of size 7)
A student of Florent Hivert had to master project to parallelize
SearchForest. Imagine what such module can need by inheritance... (with
possible adaptations according changes of SearchForest)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6812#comment:84>
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.
