如何从用户兴趣数据中找到（用户数*共享兴趣数）最大的簇

我们的核心目标是最大化「簇内用户数 × 簇内所有用户共享的兴趣数量」，本质上等价于寻找一个兴趣集合S，统计所有兴趣完全包含S的用户数量N，取len(S)*N最大的组合即可。
由于业务场景中兴趣总数远小于用户数，且单个用户的兴趣数量有限，我们可以通过枚举每个用户的所有非空兴趣子集来实现，时间复杂度可控：

1. 先把输入的(user, interest)元组转换为每个用户对应的兴趣集合，方便后续查询
2. 遍历每个用户的兴趣集合，生成其所有非空子集，统计每个子集被多少用户的兴趣集合包含
3. 遍历所有统计过的兴趣子集，计算得分子集大小 × 覆盖用户数，找到得分最高的子集
4. 最后筛选出所有包含该兴趣子集的用户，就是我们要的最大簇

import random
from itertools import combinations
from collections import defaultdict

# Generate 300 random (user, interest) tupples
def generate_data():
    data = []
    while len(data) < 300:
        # 修正原代码randint参数缺失的问题
        data_pt = {"user": random.randint(1,100), "interest":random.randint(1,50)}
        if data_pt not in data:
            data.append(data_pt)
    return data

def largest_cluster(data):
    # 步骤1：构建用户到兴趣集合的映射
    user_interests = defaultdict(set)
    for item in data:
        user_interests[item["user"]].add(item["interest"])
    
    # 步骤2：统计所有兴趣子集的覆盖用户数
    subset_count = defaultdict(int)
    for interests in user_interests.values():
        interest_list = list(interests)
        # 生成所有非空子集
        for k in range(1, len(interest_list)+1):
            for subset in combinations(interest_list, k):
                # 用frozenset做字典的键
                subset_key = frozenset(subset)
                subset_count[subset_key] += 1
    
    # 步骤3：找得分最高的兴趣子集
    max_score = -1
    best_subset = None
    for subset, count in subset_count.items():
        score = len(subset) * count
        if score > max_score:
            max_score = score
            best_subset = subset
    
    # 步骤4：筛选出所有包含最优子集的用户
    best_users = [user for user, interests in user_interests.items() if best_subset.issubset(interests)]
    
    return {
        "users": best_users,
        "shared_interests": list(best_subset),
        "score": max_score
    }

# 测试示例数据
def test_sample():
    sample_data = [
        {"user":1, "interest":2}, {"user":1, "interest":3},
        {"user":2, "interest":2}, {"user":2, "interest":3}, {"user":2, "interest":4},
        {"user":3, "interest":2}, {"user":3, "interest":3}, {"user":3, "interest":8},
        {"user":4, "interest":7},
        {"user":5, "interest":7},
        {"user":6, "interest":9},
    ]
    res = largest_cluster(sample_data)
    print("测试结果：")
    print(f"用户：{res['users']}")
    print(f"共享兴趣：{res['shared_interests']}")
    print(f"得分：{res['score']}")

if __name__ == "__main__":
    test_sample()
    # 测试随机生成的数据
    # data = generate_data()
    # print(largest_cluster(data))

运行test_sample函数就可以验证示例数据，输出结果和题目给出的正确答案完全一致：用户为[1,2,3]，共享兴趣为[2,3]，得分6。如果存在多个得分相同的最大簇，可以根据需要调整代码返回所有符合条件的结果。

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