Python中基于索引对称性移除嵌套列表重复项的通用优化方法

要解决任意索引对称规则下的列表去重问题，核心思路是给每个等价类生成唯一的"标准标识"，通过标识去重即可。下面提供两种通用方案，适配不同复杂度的对称场景：

方案一：分组置换法（适用于"索引组内可任意交换"的对称） #

如果你的对称规则是「某些索引属于同一等价组，组内元素可任意置换」（比如D4图中a/b/d/e索引可互换、c固定），这种方法最简单高效：

步骤 #

1. 定义等价索引分组：用列表嵌套表示哪些索引属于同一组，比如D4场景的分组是 [[0,1,3,4], [2]]
2. 生成标准键：对每个元素，取出每组索引对应的元素并排序，将排序后的结果组合成不可变的tuple作为唯一标识
3. 用集合记录已出现的标识，仅保留首次出现的元素

代码实现 #

from itertools import product

def get_canonical_key(el, index_groups):
    """生成元素的标准标识键"""
    key_parts = []
    for group in index_groups:
        # 取出组内元素并排序，转成tuple（保证可哈希）
        part = tuple(sorted(el[i] for i in group))
        key_parts.append(part)
    return tuple(key_parts)

# 定义你的对称索引分组（这里是D4图的例子）
index_groups = [[0,1,3,4], [2]]

# 生成原始列表
mylist = [list(i) for i in product(range(5), repeat=5) if sum(i) == 5]

# 去重过程
seen_keys = set()
newlist = []
for el in mylist:
    key = get_canonical_key(el, index_groups)
    if key not in seen_keys:
        seen_keys.add(key)
        newlist.append(el)

print(len(newlist))  # 输出去重后的数量

方案二：全置换枚举法（适用于任意对称变换） #

如果对称规则是更复杂的变换（比如旋转、反射等组合，而非简单的组内交换），可以枚举所有对称变换对应的索引排列，取变换后字典序最小的结果作为标准标识：

步骤 #

1. 定义所有对称置换：每个置换是一个tuple，表示原索引到新位置的映射（比如D4的8种对称变换）
2. 生成标准键：对每个元素，生成所有置换后的结果，取字典序最小的tuple作为唯一标识
3. 同样用集合记录标识，实现去重

代码实现 #

from itertools import product

def get_canonical_key(el, permutations):
    """生成元素的标准标识键（基于所有对称置换）"""
    # 生成所有置换后的元素
    transformed = []
    for perm in permutations:
        transformed_el = tuple(el[i] for i in perm)
        transformed.append(transformed_el)
    # 返回字典序最小的结果作为标准键
    return min(transformed)

# 定义D4图的所有对称置换（根据结构调整）
d4_permutations = [
    (0,1,2,3,4),  # 恒等变换
    (4,3,2,1,0),  # 旋转180度
    (0,3,2,1,4),  # 水平反射（左右翻转）
    (4,1,2,3,0),  # 垂直反射（上下翻转）
    (1,4,2,0,3),  # 顺时针旋转90度
    (3,0,2,4,1),  # 逆时针旋转90度
    (1,0,2,4,3),  # 对角线反射1
    (3,4,2,0,1),  # 对角线反射2
]

# 生成原始列表
mylist = [list(i) for i in product(range(5), repeat=5) if sum(i) == 5]

# 去重过程
seen_keys = set()
newlist = []
for el in mylist:
    key = get_canonical_key(el, d4_permutations)
    if key not in seen_keys:
        seen_keys.add(key)
        newlist.append(el)

print(len(newlist))  # 输出去重后的数量

方案对比 #

内容的提问来源于stack exchange，提问作者Bulkilol