#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):
Still in lex_cmp_partial: If the two list segments are equal, then each
pair of items is compared twice, namely:
{{{
for i in range(step):
if v1[i] > v2[i]:
return 1
if v1[i] < v2[i]:
return -1
}}}
Hence, if they coincide in the first 10 positions and differ in the 11th,
then 21 or 22 comparisons are needed to find the bigger vector. But if one
does
{{{
for i in range(step):
if v1[i] != v2[i]:
break
if i<step:
if v1[i]<v2[i]:
return -1
else:
return 1
return 0
}}}
then only 11 or 12 comparisons are needed.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6812#comment:73>
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.
