Opened 14 years ago

Closed 14 years ago

Last modified 14 years ago

#4341 closed enhancement (fixed)

[with patch, positive review] Optimisations + corrections to latin.py

Reported by: carlohamalainen Owned by: mhansen
Priority: minor Milestone: sage-3.2.1
Component: combinatorics Keywords:
Cc: sage-combinat Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by mabshoff)

  • Removed code that used gap.Representative in an unsafe manner (assumed that the ordering would be the same on each execution but the GAP manual says that this may not be the case). Previous code did work but was not safe.
  • Replacement tau_to_bitrade uses correct and straightforward combinatorial approach.
  • Replacement of p3_group_bitrade_generators is orders of magnitude faster; uses GAP's IsomorphismPermGroup? instead of explicitly constructing a natural homomorphism.

Attachments (1)

ch-latin.patch (35.0 KB) - added by carlohamalainen 14 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 14 years ago by wdj

This applies cleanly to 3.2 and passes sage -testall. However, I have several (possibly very stupid) questions about the docstrings, which I've passed on to the author off-list (to save myself the embarrassment of asking dumb questions:-). I prefer to wait until I hear back to give an appraisal.

Changed 14 years ago by carlohamalainen

Attachment: ch-latin.patch added

comment:2 Changed 14 years ago by wdj

Regarding the "to do" using nauty: please don't. Robert Miller's code NICE does this fine:

sage: from sage.combinat.matrices.latin import *
sage: M = matrix([(0, 1, 2, 3), (2, 3, 0, 1), (3, 2, 1, 0), (1, 0, 3, 2)])
sage: L = LatinSquare(M)
sage: L.is_latin_square()
True
sage: from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct
sage: A = MatrixStruct(M)
sage: autgp = A.automorphism_group()
sage: gens = [[j+1 for j in autgp[0][i]] for i in range(len(autgp[0]))]
sage: S4 = SymmetricGroup(4)
sage: G = PermutationGroup([S4(x) for x in gens]); G
Permutation Group with generators [(1,2)(3,4)]

An easy "to do": take the very short MOLS codes in Guava (included in Sage), at http://sage.math.washington.edu/home/wdj/guava/lib/matrices.gi, and translate it into Python/Sage?/latin.py code. (MOLS are used to construct optimal non-linear codes, but non-linear codes have not yet been implemented in Sage.)

I'm currently running tests on this (second) patch and will post again soon.

comment:3 Changed 14 years ago by wdj

Summary: [with patch, needs review] Optimisations + corrections to latin.py[with patch, positive review] Optimisations + corrections to latin.py

This looks good to me. Applies cleanly to 3.2.alpha0 and passes sage -testall.

comment:4 Changed 14 years ago by mabshoff

Description: modified (diff)

comment:5 Changed 14 years ago by mabshoff

Resolution: fixed
Status: newclosed

Merged in Sage 3.2.1.alpha1

comment:6 Changed 14 years ago by nthiery

Cc: sage-combinat added
Note: See TracTickets for help on using tickets.