带重复元素的有序列表按容差分组并删除包含性子列表的技术需求

我有一个有序列表：

L = [330.56, 330.6, 330.65, 330.7, ...]

需要按特定容差±tol对其分组：遍历每个元素，找出所有处于该元素[元素-tol, 元素+tol]区间内的元素形成子列表，之后删除被完全包含的子列表。

当前使用的代码仅检查后续元素，且未处理重复元素：

def mw_grouper(iterable):
    group = []
    for item in iterable:
        if not group or item - group[0] <= 0.05:
            group.append(item)
        else:
            yield group
            group = [item]
    if group:
        yield group

当前得到的分组结果：

R = [[330.56, 330.6], [330.65], [330.7]]

而我需要的中间分组结果是：

R = [[330.56, 330.6], [330.56, 330.6, 330.65], [330.6, 330.65, 330.7], [330.7, 330.65]]

最终要删除被包含的子列表，得到：

F = [[330.56, 330.6, 330.65], [330.6, 330.65, 330.7]]

解决方案 #

1. 生成所有符合容差的中间分组 #

利用列表有序的特性，用二分查找快速定位每个元素对应的区间边界，同时自动去重重复分组：

import bisect

def generate_all_groups(lst, tol):
    groups = []
    n = len(lst)
    for x in lst:
        lower = x - tol
        upper = x + tol
        # 找到区间左右边界的索引
        left_idx = bisect.bisect_left(lst, lower)
        right_idx = bisect.bisect_right(lst, upper)
        # 提取有序分组
        group = lst[left_idx:right_idx]
        # 避免重复添加相同分组
        if group not in groups:
            groups.append(group)
    return groups

2. 过滤被包含的子列表 #

通过判断子集关系，剔除被其他分组完全包含的子列表：

def filter_subgroups(groups):
    # 按分组长度降序排序，优先保留长分组
    sorted_groups = sorted(groups, key=lambda g: -len(g))
    result = []
    for group in sorted_groups:
        # 检查当前分组是否是已保留分组的子集
        is_subset = False
        for res_group in result:
            if set(group).issubset(set(res_group)):
                is_subset = True
                break
        if not is_subset:
            result.append(group)
    # 按原分组顺序排序输出
    result.sort(key=lambda x: groups.index(x))
    return result

完整调用示例 #

L = [330.56, 330.6, 330.65, 330.7]
tol = 0.05

# 生成中间分组
all_groups = generate_all_groups(L, tol)
print("中间分组结果：", all_groups)

# 过滤得到最终结果
final_groups = filter_subgroups(all_groups)
print("最终结果：", final_groups)

输出：

中间分组结果： [[330.56, 330.6], [330.56, 330.6, 330.65], [330.6, 330.65, 330.7], [330.65, 330.7]]
最终结果： [[330.56, 330.6, 330.65], [330.6, 330.65, 330.7]]

重复元素处理说明 #

如果列表包含重复元素（如[330.56, 330.56, 330.6]），generate_all_groups会自动跳过重复生成的分组，避免冗余处理。

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