"""
This program outputs a matrix whose determinant is the number
of domino tilings of the input region. The matrix should be fed
to Sagemath. This input format allows for computing the number of
matchings of any bipartite planar graph.
The region should be given as a pattern of V's, A's, <'s, >'s, and X's.
All characters after a percent are ignored. Currently, the input must
fit in a rectangle with 500 rows and 200 columns.
The five main symbols and their meanings are as follows:
- X: A cell occupied by an X can be covered by a domino in any of the
four cardinal directions (rightward, leftward, upward, downward).
- V: A cell occupied by a V can be covered by a domino any way but DOWN.
- A: A cell occupied by an A can be covered by a domino any way but UP.
- <: A cell occupied by a < can be covered by a domino any way but LEFT.
- >: A cell occupied by a > can be covered by a domino any way but RIGHT.
Note: A good mnemonic for these conventions comes from the fact that
if one has a region tiled by equilateral triangles
____
/\ /\
/__\/__\
\ /\ /
\/__\/
and one wishes to pair up the triangles to form a rhombus-tiling, the
triangles that look like V's are the ones that can pair (sort of) leftward,
(sort of) rightward, or upward. Etc.
There can be holes in the array of non-blank characters, and these
holes can be arbitrary. For instance, the graphs
o--o--o
| |
o o
| |
o--o--o
and
o--o--o--o
| |
o--o--o--o
are both acceptable; the former can be represented as
XXX
X X
XXX
while the latter can be represented as
AVVA
VAAV
How to call the program from sagemath:
======================================
%attach vax_sage.py
vax_string = "AVVA\nVAAV"
matchings(vax_string)
AUTHORS:
Greg Kuperberg, Jim Propp, and David Wilson
Frédéric Chapoton for the translation to sagemath.
"""
MAX_LENGTH = 202
MAX_WIDTH = 502
def matchings(vax):
"""
Compute the number of matchings of a bipartite planar graph.
The input is given in the vax format.
EXAMPLES::
sage: matchings("XXX\nX")
1
sage: matchings("AVVA\nVAAV")
2
sage: matchings("XXX\nX X\nXXX")
2
sage: matchings("XX\nXX")
2
sage: matchings("XXX\nXXX")
3
sage: matchings("XXXX\nXXXX")
5
sage: matchings("XXXXX\nXXXXX")
8
sage: matchings(" XX \nXXXX\nXXXX\n XX ")
8
sage: matchings(" XX\n XXXX\nXXXXXX\nXXXXXX\n XXXX\n XX")
64
"""
FREE = -1
# load the image
data = vax.splitlines()
data = [u.rstrip() for u in data if u.strip()]
width = max(len(u) for u in data) + 2
length = len(data) + 2
assert width < MAX_WIDTH
assert length < MAX_LENGTH
pict = [[''] * width for _ in range(length)]
p = [[0] * width for _ in range(length)]
gap_table = [[0] * width for _ in range(length)]
for i in range(length - 2):
for j in range(width - 2):
if i < len(data) and j < len(data[i]):
pict[i + 1][j + 1] = data[i][j]
# cleanup
for i in range(length):
flag = False
for j in range(width):
if pict[i][j] == '%':
flag = True
if flag or pict[i][j] not in ['X', 'A', 'V', '<', '>']:
pict[i][j] = ''
# preparation
rows = columns = 0
for i in range(length):
gaps = 1
for j in range(width):
if pict[i][j] == '':
gaps *= -1
gap_table[i][j] = gaps
if (i + j) % 2:
if pict[i][j] == '':
p[i][j] = FREE
else:
p[i][j] = columns
columns += 1
else:
if pict[i][j] == '':
p[i][j] = FREE
else:
p[i][j] = rows
rows += 1
assert rows == columns
# matrix computation
matrix_data = []
for i in range(1, length - 1):
for j in range(i % 2, width - 1, 2):
if p[i][j] != FREE:
one_column = []
for k in range(columns):
entry = 0
if (k == p[i + 1][j] and pict[i][j] != 'V' and
pict[i + 1][j] != 'A'):
entry = gap_table[i][j]
if (k == p[i - 1][j] and pict[i][j] != 'A' and
pict[i - 1][j] != 'V'):
entry = gap_table[i-1][j]
if (k == p[i][j + 1] and pict[i][j] != '>' and
pict[i][j + 1] != '<'):
entry = 1
if (k == p[i][j - 1] and pict[i][j] != '<' and
pict[i][j - 1] != '>'):
entry = -1
one_column.append(entry)
matrix_data.append(one_column)
return abs(matrix(ZZ, rows, columns, matrix_data).det())