#18987: Parallel computation for TilingSolver.number_of_solutions
-------------------------+-------------------------------------------------
Reporter: | Owner:
slabbe | Status: needs_review
Type: | Milestone: sage-6.9
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers: Vincent Delecroix
combinatorics | Work issues:
Keywords: | Commit:
Authors: | 2133ecdcffb1b993049874c8be6cad2b1224a73a
Sébastien Labbé | Stopgaps:
Report Upstream: N/A |
Branch: |
public/18987 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by slabbe):
> You are building a lot of images to consider `matrix x polyomino` to use
just one at the end. Why not
I know but I need all of them. That is what I understood yesterday. Let me
try to explain. In general it is okay to take only one matrix in the
coset. The problem comes when the polyomino is invariant under some of the
24 orientation preserving isometries of the cube. For example, consider:
{{{
sage: from sage.games.quantumino import pentaminos
sage: from sage.combinat.tiling import ncube_isometry_group
sage: p = pentaminos[7]
sage: m = ncube_isometry_group(3)[-3]
sage: p
Polyomino: [(0, 0, 0), (0, 1, 0), (0, 2, 0), (0, 2, 1), (1, 0, 0)], Color:
orange
sage: m
[ 0 0 1]
[ 0 -1 0]
[ 1 0 0]
sage: (m*p).canonical() == p
True
}}}
The polyomino `p` has 12 distinct rotation images instead of 24. And among
the 12 ways of placing that polyomino into a box, there are 3 distinct
ways up to rotation of the box keeping the box invariant. To compute this,
we need to consider the whole coset:
{{{
sage: cosets = ncube_isometry_group_modpi(3)
sage: P_coset = set(frozenset((m.matrix() * p).canonical() for m in coset)
for coset in cosets)
sage: len(P_coset)
3
sage: len(set(next(iter(s)) for s in P_coset))
3
}}}
Otherwise, you obtain too many polyominos (see below).
{{{
sage: set((coset[0].matrix() * p).canonical() for coset in cosets)
{Polyomino: [(0, 0, 1), (1, 0, 1), (1, 1, 1), (1, 2, 0), (1, 2, 1)],
Color: orange,
Polyomino: [(0, 1, 2), (1, 0, 0), (1, 1, 0), (1, 1, 1), (1, 1, 2)],
Color: orange,
Polyomino: [(0, 0, 0), (0, 1, 0), (1, 1, 0), (2, 1, 0), (2, 1, 1)],
Color: orange,
Polyomino: [(0, 1, 0), (0, 1, 1), (1, 1, 1), (2, 0, 1), (2, 1, 1)],
Color: orange,
Polyomino: [(0, 2, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 2, 0)],
Color: orange}
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18987#comment:45>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
