如何从翻唱歌曲列表生成翻唱艺人→原创艺人链并获取最长链？

问题背景 #

给定一份包含翻唱艺人、歌曲、原创艺人的列表，需要生成所有完整的翻唱艺人→原创艺人链集合，并最终找出最长的链。

示例输入 #

期望输出 #

Gyroscope->Jebediah->B. J. Thomas->Mary->Sophie
Gyroscope->Jebediah->B. J. Thomas->Mary->Lucy
Jebediah->B. J. Thomas->Mary->Sophie
Jebediah->B. J. Thomas->Mary->Lucy
B. J. Thomas->Mary->Sophie
B. J. Thomas->Mary->Lucy
Mary->Sophie
Mary->Lucy

原代码问题 #

原代码无法处理单个艺人存在多个原创关联的情况（如示例中的Mary），会把多个后续艺人合并到同一条链里，导致输出不符合预期。

解决方案 #

核心思路是递归生成所有分支链：当一个艺人有多个原创关联时，为每个关联生成独立的链分支，而非在同一条链上追加。

修改后的代码 #

# format: [['Cover Artist', 'Song', 'Original Artist'], [...]]
songs = [
    ['Gyroscope', 'Monument', 'Jebediah'],
    ['Jebediah', 'Raindrops Keep Fallin’ on My Head', 'B. J. Thomas'],
    ['B. J. Thomas', 'song 1', 'Mary'],
    ['Mary', 'song 2', 'Sophie'],
    ['Mary', 'song 3', 'Lucy']
]

def build_artist_chains(current_chain, used_indices):
    # 获取当前链最后一位艺人的所有未使用原创关联
    last_artist = current_chain[-1]
    next_links = []
    for idx, song in enumerate(songs):
        if idx not in used_indices and song[0] == last_artist:
            next_links.append((idx, song[2]))
    
    # 无后续关联时，当前链即为完整链
    if not next_links:
        return [current_chain]
    
    # 递归生成每个分支的链
    all_chains = []
    for idx, orig_artist in next_links:
        new_chain = current_chain.copy()
        new_chain.append(orig_artist)
        new_used = used_indices.copy()
        new_used.append(idx)
        all_chains.extend(build_artist_chains(new_chain, new_used))
    
    return all_chains

# 生成所有可能的链
all_artist_chains = []
for idx, song in enumerate(songs):
    initial_chain = [song[0], song[2]]
    chains_from_initial = build_artist_chains(initial_chain, [idx])
    all_artist_chains.extend(chains_from_initial)

# 转换为字符串并去重，按链长倒序排序（可选）
unique_chains = list(set('->'.join(chain) for chain in all_artist_chains))
unique_chains.sort(key=lambda x: len(x), reverse=True)

# 输出结果
for chain in unique_chains:
    print(chain)

代码说明 #

1. 递归分支处理：build_artist_chains函数会为当前艺人的每个未使用关联生成独立的链副本，递归扩展每个分支，确保每个关联生成单独的链。
2. 避免重复条目：通过used_indices记录已使用的歌曲索引，防止循环引用或重复生成链。
3. 链整理：最后收集所有链并去重，可选按长度排序，便于快速定位最长链。

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