构建0/1二维矩阵的旋转镜像无关无碰撞唯一识别函数

核心逻辑 #

这事儿本质是生成矩阵在二面体群D₄（含4种旋转+4种镜像翻转，共8种变换）下的等价类唯一标识。要实现无碰撞，关键是给每个等价类指定一个唯一的「标准代表」，再基于这个代表生成标识——同一等价类的矩阵无论怎么旋转镜像，最终都会映射到同一个标准代表，不同等价类的标准代表必然不同。

具体实现步骤 #

1. 生成所有8种变换后的矩阵 #

先实现矩阵的8种基础变换：

• 原矩阵（0°旋转）
• 顺时针旋转90°
• 顺时针旋转180°
• 顺时针旋转270°
• 水平镜像翻转
• 水平镜像后顺时针旋转90°
• 水平镜像后顺时针旋转180°
• 水平镜像后顺时针旋转270°

变换实现参考：比如顺时针90°旋转时，原矩阵的(i,j)位置元素会对应到新矩阵的(j, n-1-i)（n为矩阵边长，8×8则n=8）。

2. 确定等价类的标准代表 #

把8种变换后的矩阵转换成可比较的标准化形式，再选其中的「最小值」作为标准代表：

• 标准化方式：将矩阵按行优先展平为0/1字符串，或者直接转成64位整数（8×8共64个布尔值，刚好适配64位无符号整数）。
• 取最小值：比如对8个展平后的字符串取字典序最小的，或者对8个整数取数值最小的——这个最小值就是整个等价类的唯一标识。

3. 无碰撞标识生成 #

因为8×8矩阵最多只有64位数据，用64位整数完全可以无碰撞存储单个矩阵的展平值。同一等价类的8个变换对应的整数中，最小值是唯一的；不同等价类的最小值不可能重复（否则两个矩阵属于同一等价类，矛盾）。

代码示例（Python） #

def matrix_to_uint64(matrix):
    """把8×8布尔矩阵转成64位无符号整数"""
    val = 0
    for row in matrix:
        for bit in row:
            val = (val << 1) | (1 if bit else 0)
    return val

def rotate_90(matrix):
    """顺时针旋转90°"""
    n = len(matrix)
    return [[matrix[n-1-j][i] for j in range(n)] for i in range(n)]

def flip_horizontal(matrix):
    """水平镜像翻转"""
    return [row[::-1] for row in matrix]

def get_all_transforms(matrix):
    """生成8种变换后的矩阵"""
    transforms = []
    current = matrix
    # 添加4种旋转
    for _ in range(4):
        transforms.append(current)
        current = rotate_90(current)
    # 添加4种镜像+旋转
    flipped = flip_horizontal(matrix)
    current = flipped
    for _ in range(4):
        transforms.append(current)
        current = rotate_90(current)
    return transforms

def get_unique_identifier(matrix):
    """生成旋转镜像不变的唯一标识符"""
    all_vals = [matrix_to_uint64(m) for m in get_all_transforms(matrix)]
    return min(all_vals)

内容的提问来源于stack exchange，提问作者F.P