import itertools
import matplotlib.pyplot as plt

# D4二面体群8个置换（0-based顶点）
permutations = [
    [0, 1, 2, 3],       # 恒等
    [3, 0, 1, 2],       # 旋转90°
    [2, 3, 0, 1],       # 旋转180°
    [1, 2, 3, 0],       # 旋转270°
    [3, 2, 1, 0],       # 翻转：对边中点
    [1, 0, 3, 2],       # 翻转：对边中点
    [0, 3, 2, 1],       # 翻转：对角线
    [2, 1, 0, 3],       # 翻转：对角线
]

def apply_perm(state, perm):
    return tuple(state[p] for p in perm)

def get_canonical(state):
    variants = [apply_perm(state, p) for p in permutations]
    return min(variants)

# 枚举全部16种染色
all_states = list(itertools.product([0,1], repeat=4))
equivalence_classes = {}
for s in all_states:
    rep = get_canonical(s)
    if rep not in equivalence_classes:
        equivalence_classes[rep] = []
    equivalence_classes[rep].append(s)

classes_list = list(equivalence_classes.values())
print(f"等价类总数 = {len(classes_list)}")

# 绘图
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.figure(figsize=(12, 6))
vertex_pos = [ (1,1), (1,-1), (-1,-1), (-1,1) ]
n_class = len(classes_list)
cols = 5
rows = (n_class + cols -1)//cols

for i, one_class in enumerate(classes_list):
    ax = plt.subplot(rows, cols, i+1)
    state = one_class[0]
    xs = [vertex_pos[v][0] for v in range(4)]
    ys = [vertex_pos[v][1] for v in range(4)]
    ax.plot(xs + [xs[0]], ys + [ys[0]], color='black')
    for vid in range(4):
        c = 'black' if state[vid]==0 else 'white'
        ax.scatter(xs[vid], ys[vid], s=300, facecolor=c, edgecolor='black', zorder=5)
    ax.set_title(f'方案{i+1}')
    ax.set_xlim(-1.5,1.5)
    ax.set_ylim(-1.5,1.5)
    ax.set_aspect('equal')
    ax.axis('off')

plt.tight_layout()
plt.show()

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com