如何基于长度容差对可循环移位的向量-长度列表分组？

核心思路 #

• 先按边数（列表长度）预分组：不同边数的形状不可能互为循环移位，直接排除同组可能
• 对同边数的形状，判断是否存在某个循环移位量，使得移位后每条边的长度差都在设定容差内
• 用标记法避免重复分组，遍历每个未分组的形状，把所有符合条件的归为一组

具体步骤 #

1. 按边数拆分集合
   把所有形状按边数分成不同的子集合，比如3边的放一起，4边的放一起，不同边数的直接不做对比，节省时间。

2. 写一个循环移位匹配函数
   这个函数接收两个同边数的形状列表、容差值，返回是否满足循环移位且长度差符合要求：

• 先提取两个形状的所有边长度
• 将第二个形状的长度列表拼接成长度列表+长度列表，这样任何循环移位后的序列都是这个拼接列表的连续子序列
• 遍历所有可能的移位位置，检查对应位置的长度差是否都在容差内

3. 执行分组

• 初始化一个集合记录已分组的形状索引
• 遍历每个边数子集合，对每个未标记的形状，找到所有同集合内符合匹配条件的形状，组成一组并标记索引

示例代码（Python） #

def is_cyclic_length_match(shape_a, shape_b, tolerance):
    if len(shape_a) != len(shape_b):
        return False
    # 提取两条形状的边长度
    lengths_a = [edge[1] for edge in shape_a]
    lengths_b = [edge[1] for edge in shape_b]
    # 拼接b的长度列表，方便检查循环移位
    doubled_b_lengths = lengths_b * 2
    n = len(lengths_a)
    
    # 遍历所有可能的移位量
    for shift in range(n):
        match = True
        for i in range(n):
            if abs(lengths_a[i] - doubled_b_lengths[shift + i]) > tolerance:
                match = False
                break
        if match:
            return True
    return False

def group_cyclic_shapes(shapes, tolerance):
    groups = []
    used_indices = set()
    # 按边数预分组
    shape_groups_by_len = {}
    for idx, shape in enumerate(shapes):
        edge_count = len(shape)
        if edge_count not in shape_groups_by_len:
            shape_groups_by_len[edge_count] = []
        shape_groups_by_len[edge_count].append((idx, shape))
    
    # 处理每个边数组
    for edge_count in shape_groups_by_len:
        current_shapes = shape_groups_by_len[edge_count]
        for idx_a, shape_a in current_shapes:
            if idx_a in used_indices:
                continue
            # 组建当前组
            current_group = [idx_a]
            used_indices.add(idx_a)
            # 找所有匹配的形状
            for idx_b, shape_b in current_shapes:
                if idx_b in used_indices:
                    continue
                if is_cyclic_length_match(shape_a, shape_b, tolerance):
                    current_group.append(idx_b)
                    used_indices.add(idx_b)
            groups.append(current_group)
    return groups

# 测试示例
test_shapes = [
    [(1, 2.0), (0, 3.0), (-1, 2.0), (0, 3.0)],  # 0号
    [(0, 3.0), (-1, 2.0), (0, 3.0), (1, 2.0)],  # 1号（循环移位）
    [(1, 1.0), (1, 1.0), (-1, 1.0)],            # 2号（3边）
    [(2, 5.0), (-2, 5.0), (0, 5.0), (0, 5.1)]   # 3号（4边但长度不匹配）
]
print(group_cyclic_shapes(test_shapes, 0.1))  # 输出 [[0, 1], [2], [3]]

关键细节 #

• 按边数预分组：直接过滤掉不可能匹配的情况，大幅减少对比次数
• 拼接列表检查循环移位：避免了复杂的模运算，逻辑更直观
• 容差严格对应：确保只有移位后每条边的长度都在允许误差内的形状才会被归为一组，符合你的需求

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