""" 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())