#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 SimonKing):
With the patch that I almost finished (not posted yet), I get
{{{
sage: TEST_generation_orbit_sum(TransitiveGroup(8,1), verbose=True)
For G be the transitive group number 1 of degree 8
Cardinality of G : 8
Cardinality of secondary invariants : 5040
Number of canonical monomials under staircase : 18297
Total time : 1.49698710442
-------------------------------------
(1.4969871044158936, 18297, 8)
sage: TEST_generation_orbit_sum(TransitiveGroup(9,1), verbose=True)
For G be the transitive group number 1 of degree 9
Cardinality of G : 9
Cardinality of secondary invariants : 40320
Number of canonical monomials under staircase : 153974
Total time : 13.5961458683
-------------------------------------
(13.596145868301392, 153974, 9)
sage: TEST_generation_orbit_sum(TransitiveGroup(10,1), verbose=True)
For G be the transitive group number 1 of degree 10
Cardinality of G : 10
Cardinality of secondary invariants : 362880
Number of canonical monomials under staircase : 1452325
Total time : 140.386005878
-------------------------------------
(140.3860058784485, 1452325, 10)
sage: G = TransitiveGroup(15,28)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: timeit('S._cardinality_from_iterator()')
5 loops, best of 3: 415 ms per loop
}}}
Without the patch, I get
{{{
sage: TEST_generation_orbit_sum(TransitiveGroup(8,1), verbose=True)
For G be the transitive group number 1 of degree 8
Cardinality of G : 8
Cardinality of secondary invariants : 5040
Number of canonical monomials under staircase : 18297
Total time : 1.58537387848
-------------------------------------
(1.585373878479004, 18297, 8)
sage: TEST_generation_orbit_sum(TransitiveGroup(9,1), verbose=True)
For G be the transitive group number 1 of degree 9
Cardinality of G : 9
Cardinality of secondary invariants : 40320
Number of canonical monomials under staircase : 153974
Total time : 15.0423038006
-------------------------------------
(15.042303800582886, 153974, 9)
sage: TEST_generation_orbit_sum(TransitiveGroup(10,1), verbose=True)
For G be the transitive group number 1 of degree 10
Cardinality of G : 10
Cardinality of secondary invariants : 362880
Number of canonical monomials under staircase : 1452325
Total time : 162.007292032
-------------------------------------
(162.00729203224182, 1452325, 10)
sage: G = TransitiveGroup(15,28)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: timeit('S._cardinality_from_iterator()')
5 loops, best of 3: 933 ms per loop
}}}
So, it is roughly 10% to 50% improvement (even though I am currently still
converting the set to sorted lists).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6812#comment:81>
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.
