Program to show that no perfect 1-factorization for K_{4,4,4}
def cond_perm(X, cond):
L = [[]]
for c in cond:
L_tmp = L
L = []
for l in L_tmp:
for x in set(X)-set(c)-set(l):
L.append(l+[x])
return L
def one_factor(L3AD, i):
n = len(L3AD[0])
x_axis = ['x'+str(k) for k in range(1,n+1)]
y_axis = ['y'+str(k) for k in range(1,n+1)]
z_axis = ['z'+str(k) for k in range(1,n+1)]
one_f = {}
for r in range(n):
c = (L3AD[1][r]+[i]).index(i)
if c < n:
x, y = x_axis[-c-1], y_axis[-r-1]
one_f[x], one_f[y] = y, x
z, xy = z_axis[r], (x_axis[::-1]+y_axis)[L3AD[0][r].index(i)]
one_f[z], one_f[xy] = xy, z
return one_f
def cycle(L3AD, i1, i2, vertex):
one_factor_1 = one_factor(L3AD, i1)
one_factor_2 = one_factor(L3AD, i2)
cyc = []
while vertex not in cyc:
cyc.append(vertex)
vertex = one_factor_1[vertex]
cyc.append(vertex)
vertex = one_factor_2[vertex]
return cyc
def check_P1F(L3AD):
n = len(L3AD[0])
for i in range(1,2*n+1):
for j in range(i+1,2*n+1):
if len(cycle(L3AD, i, j, 'x1')) < 3*n:
return False
return True
Y = list(range(1,9))
for t_row1 in cond_perm(set(Y)-{8},zip(Y[:4])):
c1 = list(zip(Y[:4],t_row1))
for t_row2 in cond_perm(set(Y)-{7},c1):
c2 = list(zip(Y[:4],t_row1,t_row2))
Y2_ = {i for i in Y if (t_row1+t_row2).count(i)>=2}
for t_row3 in cond_perm(set(Y)-{6}-Y2_,c2):
c3 = list(zip(Y[:4],t_row1,t_row2,t_row3))
Y3_ = {i for i in Y if (t_row1+t_row2+t_row3).count(i)>=2}
for t_row4 in cond_perm(set(Y)-{5}-Y3_,c3):
c4_1 = list(zip(Y[:4],t_row1,t_row2,t_row3,t_row4))
c4_2 = [[5]+t_row4,
[6]+t_row3,
[7]+t_row2,
[8]+t_row1]
for s_row2 in cond_perm(set(Y),c4_1+c4_2):
c5_1 = list(zip(Y[:4],t_row1,t_row2,t_row3,t_row4,s_row2[:4]))
c5_2 = [[5]+t_row4+[s_row2[4]],
[6]+t_row3+[s_row2[5]],
[7]+t_row2+[s_row2[6]],
[8]+t_row1+[s_row2[7]]]
for s_row3 in cond_perm(set(Y),c5_1+c5_2):
c6_1 = list(zip(Y[:4],t_row1,t_row2,t_row3,t_row4,s_row2[:4],s_row3[:4]))
c6_2 = [[5]+t_row4+[s_row2[4]]+[s_row3[4]],
[6]+t_row3+[s_row2[5]]+[s_row3[5]],
[7]+t_row2+[s_row2[6]]+[s_row3[6]],
[8]+t_row1+[s_row2[7]]+[s_row3[7]]]
for s_row4 in cond_perm(set(Y),c6_1+c6_2):
L3AD = [[Y,s_row2,s_row3,s_row4],
[t_row1,t_row2,t_row3,t_row4]]
print(*L3AD[0],*L3AD[1], sep="¥n")
if(check_P1F(L3AD)):
print('perfect')
exit()
else:
print('non-perfect')
Program to count the number of Latin regular hexahedra of order 2
N = 2
X = list(range(1,4*N+1))
def cond_perm(X, cond):
L = [[]]
for c in cond:
L_tmp = L
L = []
for l in L_tmp:
for x in set(X)-set(c)-set(l):
L.append(l+[x])
return L
def contra(circuit):
c = []
for i in [2,3,0,1]:
c += circuit[(i+1)*N-1:i*N-1 if i>0 else None:-1]
return c
def top_bottom(side):
tb_list = [[]]
cond = list(map(list,zip(*side,*map(contra,side))))
c = cond[N:2*N]*2
for i in range(N):
tb_list_tmp = tb_list
tb_list = []
for tb in tb_list_tmp:
if tb_list_tmp != [[]]:
add_c = list(map(list,zip(*tb)))
c = [c[j]+add_c[j]+add_c[j+N] for j in range(N)]*2
for row in cond_perm(set(X)-set(cond[i]),c):
tb_list.append(tb+[row])
return tb_list
def formalize_top_bottom(tb):
return [[tb[i][:N] for i in range(N)], [tb[i][N:] for i in reversed(range(N))]]
def L_list(n, X):
side_list = [[X]]
for _ in range(n-1):
side_list_tmp = side_list
side_list = []
for s in side_list_tmp:
for circ in cond_perm(X,zip(*s,*map(contra,s))):
side_list.append(s+[circ])
L_list, L_list_upto_tb_trans = [], []
for side in side_list:
tb_list = top_bottom(side)
L_list += [side+[tb] for tb in tb_list]
if len(tb_list)>0:
L_list_upto_tb_trans += [side+[tb_list[0]]]
L_list_upto_trans = []
for L in L_list_upto_tb_trans:
flag = False
a = list(map(set,zip(L[1][:4],contra(L[1])[:4])))
for i in range(len(L_list_upto_trans)):
if a == list(map(set,zip(L_list_upto_tb_trans[i][1][:4],contra(L_list_upto_tb_trans[i][1])[:4]))):
flag = True
break
if flag is False:
L_list_upto_trans.append(L)
return L_list, L_list_upto_tb_trans, L_list_upto_trans
def display(L):
print(' '*N+'+'+'-'*(2*N-1)+'+')
for t in formalize_top_bottom(L[2])[0]:
print(' '*N+'|'+' '.join(map(str, t))+'|')
print(('+'+'-'*(2*N-1))*4+'+')
for i in range(N):
print('|'+(('{} '*(N-1)+'{}|')*4).format(*L[i]))
print(('+'+'-'*(2*N-1))*4+'+')
for b in formalize_top_bottom(L[2])[1]:
print(' '*N+'|'+' '.join(map(str, b))+'|')
print(' '*N+'+'+'-'*(2*N-1)+'+')
L_set, _, L_f = L_list(N, X)
print(len(L_f))
for L in L_f:
display(L)
print(len(L_set)*8*7*6*5*4*3*2)