本题是lattice animal enumeration问题，题面中$n\le 15$的情况可以用深度有限搜索直接生成全部的n阶雕塑计算，但$n=18$时雕塑的数量非常多，无法存储所有的状态。
对于这一问题，存在一些比较成熟的算法，比如Redelmeier算法。以下解答改编自Github中的这一实现。
贴中的原代码在第一象限中生成所有n阶雕塑，且最低部格子的纵坐标总是0。
此处修改了count_fixed_polyominoes方法中if len(p)==n之中的部分，找到n阶雕塑后先计算质心的x坐标mass，再把整个图形横移mass个单位，若(mass,0)处有格子，就说明可以以此作为基座产生一个满足要求的平衡雕塑。
接下来判断该图形是否对称，若对称则总数+2，否则总数+1，最后把总数除以2输出即得结果$15030564$。
注：按原贴的实现，以下为Python 3代码，此代码耗时很长，需要耐心等待，代码中打印了进度信息，并保留了原注释。
target=18
"""
Python implementation based on [1] to count the number of fixed polyominoes [2].
No need for extra libraries, apart from the optional pprint
whose role is to "pretty print" a graph.
Tested on Python 3.9.4
[1] https://louridas.github.io/rwa/assignments/polyominoes/
[2] Redelmeier, D. Hugh. "Counting polyominoes: yet another attack."
Discrete Mathematics 36.2 (1981): 191-203.
"""
#import pprint # optional library
def neighbors(p, u, v): # check if node v is a neighbor of u , but v is untried
"""
Function to check if Node v is a neighbor of u.
"""
for i in p:
if i == u:
continue
upper = (i[0], i[1]+1)
down = (i[0], i[1]-1)
right = (i[0]+1, i[1])
left = (i[0]-1, i[1])
if v in (right, upper, down, left):
return True
return False
def count_fixed_polyominoes(g, n, untried=None, p=None, r=0):
"""
Implemented as closely as possible to the pseudocode found at:
https://louridas.github.io/rwa/assignments/polyominoes/count_fixed_polyominoes_algorithm_nc.png
Complexity of this algorithm is exponential and is recursive.
Input:
g: a G(V,E) graph-square lattice in dictionary form,
generated by create_polyomino_graph().
n: number of tiles of the polyomino. Otherwise called
size of polyomino.
untried: the not yet examined/tried set of nodes of g.
p: the current polyomino.
Output:
r: the number of fixed polyominoes of size n.
Notes
-----
This implementation is pretty slow for size n > 15. Check out Jensen's [1]
faster but still exponential algorithm.
[1] Jensen, Iwan. "Enumerations of lattice animals and trees.",
Journal of statistical physics 102.3 (2001): 865-881.
"""
if p is None: # to avoid default arg list or dict
p = []
untried = {(0, 0)}
untried = list(untried)
while not len(untried) == 0:
u = untried[0]
p.append(u)
untried.remove(u)
if len(p)==n:
mass=sum(x for x,y in p)
if mass%n==0:
mass=mass//n
p1=set([(x-mass,y) for x,y in p])
p2=set([(mass-x,y) for x,y in p])
if (0,0) in p1:
#print(p1)
r=r+1+(p1==p2)
if r%tick==0:print("r hits",r//tick,"x 100K")
else:
new_neighbors = []
for v in g[u]:
if (v not in untried) and (v not in p) and (not neighbors(p, u, v)):
new_neighbors.append(v)
new_untried = untried+new_neighbors
r = count_fixed_polyominoes(G, n, new_untried, p, r)
p.remove(u)
return r
def create_polyomino_graph(n):
"""
Function to create a square lattice for this problem.
For every (x,y) tile in it:
{(x,y)|(y>0) or (y=0) and x>=0}
An example is available at:
https://louridas.github.io/rwa/assignments/polyominoes/lattice_pentominoes.png
Input:
n: the size of polyomino
Output:
A dictionary in which every key (node) is paired with values (neighboring nodes)
"""
polyominograph = {}
limit = n-2
# bottom part is half
for x in range(0, n):
polyominograph[(x, 0)] = []
# all other lines are "full"
for y in range(1, n):
for x in range(-limit, limit+1):
polyominograph[(x, y)] = []
limit -= 1
for node, neighbor_list in polyominograph.items():
upper = (node[0], node[1]+1)
down = (node[0], node[1]-1)
right = (node[0]+1, node[1])
left = (node[0]-1, node[1])
if right in polyominograph:
neighbor_list.append(right)
if upper in polyominograph:
neighbor_list.append(upper)
if left in polyominograph:
neighbor_list.append(left)
if down in polyominograph:
neighbor_list.append(down)
return polyominograph
tick=100000
G=create_polyomino_graph(target)
print(count_fixed_polyominoes(G,target)//2)
|
