Python算法实现：不使用set与字典按完全相同爱好对人群分组

现有存储人员及对应爱好的数据集，每条数据为元组结构，首个元素是姓名，第二个元素是该人员的爱好列表。需要基于爱好对人群分组，爱好完全一致的人员归属同一组。

示例数据集 #

hobbies_list= [
                ("Amy", ["painting", "swimming", "listening to music"]),
                ("Bob", ["swimming", "football","basketball","water polo"]),
                ("Cindy", ["swimming", "listening to music", "painting"]),
                ("David", ["table tennis", "basketball", "volleyball"]),
                ("Edward", ["tennis", "basketball", "volleyball", "water polo"]),
                ("Frank", ["table tennis", "volleyball", "basketball"]),
                ("George", ["volleyball", "basketball", "table tennis"])
        ]

预期输出 #

-------------------------------
|Group 1 | Amy, Cindy          |
--------------------------------
|Group 2 | Bob                 |
--------------------------------
|Group 3 | David, Frank, George |
---------------------------------
|Group 4 | Edward               |
---------------------------------

实现约束 #

• 不允许使用set和字典数据结构
• 时间复杂度要求为O(MN)，其中N为hobbies_list的长度，M为单个人所有爱好的最大总字符数（本例中M为35，对应最长爱好列表["tennis", "basketball", "volleyball", "water polo"]的总字符数）

1. 标准化爱好标识：由于爱好的顺序不影响分组结果，先对每个人的爱好列表做字典序排序，再用不会出现在爱好内容中的特殊分隔符（如|）拼接为唯一字符串，作为该爱好组合的签名，相同爱好组合的签名完全一致，生成签名的时间复杂度为O(M) per person。
2. 分组匹配：维护两个一一对应的列表，分别存储已出现的爱好签名、对应组的成员列表。处理每个人时，生成其签名后遍历已有签名列表匹配对应组，匹配成功则将姓名加入对应成员列表，匹配失败则新增组。
3. 复杂度优化：签名比对前先判断长度是否一致，长度不同直接跳过，绝大多数不匹配场景可在O(1)时间完成判断，总字符比对量不超过MN，符合O(MN)的时间要求。

def group_by_hobbies(hobbies_list):
    group_signatures = []
    group_members = []
    separator = "|"

    for name, hobbies in hobbies_list:
        # 生成标准化签名
        sorted_hobbies = sorted(hobbies)
        current_signature = separator.join(sorted_hobbies)
        current_sig_len = len(current_signature)

        # 匹配已有分组
        matched_idx = -1
        for i in range(len(group_signatures)):
            # 先比长度快速过滤不匹配项
            if len(group_signatures[i]) != current_sig_len:
                continue
            if group_signatures[i] == current_signature:
                matched_idx = i
                break
        
        if matched_idx == -1:
            group_signatures.append(current_signature)
            group_members.append([name])
        else:
            group_members[matched_idx].append(name)
    
    # 格式化输出
    for group_id, members in enumerate(group_members, 1):
        member_str = ", ".join(members)
        print("-" * 40)
        print(f"|Group {group_id} | {member_str:<25}|")
    print("-" * 40)

# 测试调用
if __name__ == "__main__":
    hobbies_list= [
                ("Amy", ["painting", "swimming", "listening to music"]),
                ("Bob", ["swimming", "football","basketball","water polo"]),
                ("Cindy", ["swimming", "listening to music", "painting"]),
                ("David", ["table tennis", "basketball", "volleyball"]),
                ("Edward", ["tennis", "basketball", "volleyball", "water polo"]),
                ("Frank", ["table tennis", "volleyball", "basketball"]),
                ("George", ["volleyball", "basketball", "table tennis"])
        ]
    group_by_hobbies(hobbies_list)

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