如何利用Radix Sort实现相同电影喜好用户分组？解决顺序差异

嘿，这个问题挺有意思的！我来一步步给你拆解思路，尤其是解决「电影顺序不同但内容一致」的核心问题，再结合基数排序实现分组。

核心思路铺垫：先解决顺序问题 #

首先，你得明白：要让Ace和Jack被判定为喜好相同，必须先把他们的电影列表转换成完全一致的“签名”——不管原来的顺序如何，相同的电影集合要生成同一个key。这是基数排序能生效的前提，因为基数排序是基于key的有序性来分组的。

具体怎么做？很简单：

• 把每个用户的电影字符串拆分成列表
• 对列表按固定规则排序（比如字母顺序）
• 再把排序后的列表拼接成一个统一格式的字符串（比如用逗号分隔）

举个例子：

• Ace的电影列表是["FANTASTIC FOUR", "IRONMAN"]，排序后还是原样，拼接成"FANTASTIC FOUR, IRONMAN"
• Jack的电影列表是["IRONMAN", "FANTASTIC FOUR"]，排序后和Ace的一样，拼接出的key也完全相同
• Jane的列表排序后是["EXOTIC WILDLIFE", "NARNIA", "TRANSFORMERS"]，生成独有的key

这样一来，所有喜好相同的用户都会有同一个key，接下来用基数排序对这些（key, 用户）对排序，相同key的条目就会挨在一起，轻松分组。

用基数排序实现分组的步骤 #

基数排序的核心是按“位”逐次排序，这里的“位”可以是key字符串的每个字符。我们从最后一个字符（最低位）开始，依次往前处理，每一轮把条目按当前字符分到对应的桶里，再按桶的顺序收集，最终就能得到有序的结果。

步骤1：解析输入并生成标准化key #

先把文件里的内容读出来，给每个用户生成对应的标准化key：

# 读取用户电影数据
user_movie_data = {}
with open("user_movies.txt", "r") as f:
    for line in f:
        line = line.strip()
        if not line:
            continue
        username, movies_str = line.split(": ")
        movies_list = movies_str.split(", ")
        user_movie_data[username] = movies_list

# 生成标准化key和分组映射
key_map = {}  # key: 标准化电影字符串，value: [用户列表]
movie_map = {}  # 保存key对应的原始电影集合（用于输出）
for name, movies in user_movie_data.items():
    sorted_movies = sorted(movies)
    standard_key = ", ".join(sorted_movies)
    if standard_key not in key_map:
        key_map[standard_key] = []
        movie_map[standard_key] = sorted_movies
    key_map[standard_key].append(name)

步骤2：实现基数排序对key排序 #

接下来我们用基数排序对所有的standard_key进行排序，这样相同的key会集中在一起：

def radix_sort_for_keys(key_list):
    if not key_list:
        return []
    
    # 找到最长key的长度，短key用空格补全（保证每一轮排序的位对齐）
    max_key_length = max(len(key) for key in key_list)
    padded_keys = [(key.ljust(max_key_length), key) for key in key_list]
    
    # 从最后一位到第一位逐位排序
    for position in range(max_key_length - 1, -1, -1):
        # 创建ASCII码对应的桶（共256个，覆盖所有可见字符）
        buckets = [[] for _ in range(256)]
        for padded_key, original_key in padded_keys:
            # 获取当前位的字符，转成ASCII码作为桶的索引
            char_code = ord(padded_key[position])
            buckets[char_code].append((padded_key, original_key))
        
        # 按桶的顺序重新收集元素，作为下一轮排序的输入
        padded_keys = []
        for bucket in buckets:
            padded_keys.extend(bucket)
    
    # 提取排序后的原始key
    sorted_keys = [original_key for _, original_key in padded_keys]
    return sorted_keys

步骤3：分组输出结果 #

最后，遍历排序后的key，把用户数≥2的组输出：

# 获取排序后的key列表
sorted_standard_keys = radix_sort_for_keys(list(key_map.keys()))

# 输出符合要求的分组
for key in sorted_standard_keys:
    users = key_map[key]
    if len(users) >= 2:
        print(f"Movies: {key}")
        print(f"Partners: {', '.join(users)}")
        print()

为什么这样能行？ #

• 预处理的排序步骤彻底解决了电影顺序不同的问题，保证相同喜好的用户有完全一致的key
• 基数排序通过逐位排序，把相同的key集中在一起，遍历的时候就能轻松识别出用户组
• 如果你不想用字典先分组，也可以直接对（key, username）的元组做基数排序，排序后遍历元组列表，把连续相同key的用户归为一组，逻辑是一样的

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