【Python】【原创】魔方群置换与生成元

白冥 · 发表于 2025-2-26 19:02:40

本帖最后由白冥于 2025-2-26 19:58 编辑

目录

概述
核心功能
类结构与方法
Cube 类（小立方体类）
MagicCube 类（魔方类）
原理
算法复杂度
使用示例

概述

      本帖实现了一个3x3魔方的抽象模型，通过面向对象的方式模拟魔方的立方体块（Cube）和整体结构（MagicCube）。核心目标是为魔方状态跟踪、旋转操作及算法研究提供基础框架。本帖代码均由本人写就。

核心功能

支持六种基础面旋转（U/F/R/L/B/D）
自动维护立方体块的邻接关系
实时跟踪各块的面归属状态
提供可扩展的置换规则接口

类结构与方法
      Cube 类
         ├ __init__ 构造方法
         ├ _set_group 私有方法
         ├ binding 方法
         ├ get_group 方法
         ├ observe 方法
         └ group_permutation 方法
      MagicCube 类
         ├ __init__ 构造方法
         ├ _build_cube 私有方法
         ├ get_magic_cube 方法
         ├ face 方法
         ├ _group_permutation 私有方法
         ├ U 方法
         ├ F 方法
         ├ R 方法
         ├ L 方法
         ├ B 方法
         └ D 方法

Cube 类（小立方体类）
      表示单个立方体块，负责维护自身状态和相邻块关系。

class Cube:
def __init__(self, x: int, y: int, z: int):
if not (-1 <= x <= 1 and -1 <= y <=1 and -1 <= z <= 1):
raise ValueError("超出范围")
self._group = self._set_group(x,y,z)
self._permutation_matrix = [
[0, 2, 4, 1, 3, 5],
[3, 1, 0, 5, 4, 2],
[1, 5, 2, 3, 0, 4],
[4, 0, 2, 3, 5, 1],
[2, 1, 5, 0, 4, 3],
[0, 3, 1, 4, 2, 5]
]
self._bind=None
self._cube_group=None
def _set_group(self,x,y,z):
faces = [z == 1, x == 1, y == 1, y == -1, x == -1, z == -1]
return [(idx if faces[idx] else None) for idx in range(6)]
def binding(self, bind):
if self._bind is not None:
raise ValueError("重复操作")
self._bind=bind
def get_group(self):
return self._group
def observe(self, permutation):
next = self._bind[permutation]
group = next.get_group()
self._cube_group = group[:]
def group_permutation(self, permutation):
pg = self._permutation_matrix[permutation]
self._group = [self._cube_group[next] for next in pg]

复制代码

      关键方法：
      binding(self, bind)：
      功能：绑定扭转面的块
      observe(self, permutation)：
      功能：根据生成元信息获取绑定块的属性
      group_permutation(self, permutation)：
      功能：群置换
MagicCube 类（魔方类）

class MagicCube:
def __init__(self):
self._cube = self._build_cube()
def _build_cube(self):
cubes = {(x, y, z): Cube(x, y, z) for x in [-1, 0, 1] for y in [-1, 0, 1] for z in [-1, 0, 1]}
for crood, cube in cubes.items():
x, y, z = crood
bind = [cubes[(-y,x,1)], cubes[(1,-z,y)], cubes[(z,1,-x)], cubes[(-z,-1,x)], cubes[(-1,z,-y)], cubes[(y,-x,-1)]]
cube.binding(bind)
def get_magic_cube(self):
return self._cube
def face(self, permutation):
cubes = []
for crood, cube in self._cube.items():
x, y, z = crood
faces = [z == 1, x == 1, y == 1, y == -1, x == -1, z == -1]
if faces[permutation]:
cubes.append(cube)
return cubes
def _group_permutation(self, permutation):
cubes = self.face(permutation)
for cube in cubes:
cube.observe(permutation)
for cube in cubes:
cube.group_permutation(permutation)
def U(self):
self._group_permutation(0)
def F(self):
self._group_permutation(1)
def R(self):
self._group_permutation(2)
def L(self):
self._group_permutation(3)
def B(self):
self._group_permutation(4)
def D(self):
self._group_permutation(5)

复制代码

      关键方法：
      _group_permutation(self, permutation)：
      功能：
         1、收集目标面所有块
         2、通知每个块使用的生成元
         3、群置换
      U/F/R/L/B/D(self)：
      功能：扭转上/前/右/左/后/下面，充当魔方置换循环群的生成元

原理
      根据笛卡尔坐标系的旋转变换，绑定变换与扭转变换反向，以块(1,1,-1)的F操作为例：
      原始坐标：(x=1, y=1, z=-1)
      F旋转（绕X轴顺时针转90°）后的新坐标：(1,1,-1) → (1,1,1)
      则(1,1,1)块继承(1,1,-1)块的状态

算法复杂度
      时间复杂度：每次面扭转后仅影响4个边块和4个角块，总体时间复杂度为O(1)
      空间复杂度：存储27个Cube对象，每个包含6个绑定，总内存消耗约27*6=162个整型索引

使用示例