如何将列表的子列表中元组按连续关联序列排序？

问题场景 #

我有一个嵌套列表，每个子列表包含若干元组（可替换为列表），示例前20项如下：

list_one[:20]
>>>
[[('Bacterium', 'Biologically Active Substance'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Pharmacologic Substance', 'Immunologic Factor')],
 [('Bacterium', 'Biologically Active Substance'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Pharmacologic Substance', 'Organic Chemical')],
 [('Bacterium', 'Biologically Active Substance'),
  ('Biologically Active Substance', 'Pathologic Function'),
  ('Pathologic Function', 'Finding')],
 [('Pharmacologic Substance', 'Immunologic Factor'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Chemical', 'Biologically Active Substance')],
 [('Pharmacologic Substance', 'Organic Chemical'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Chemical', 'Biologically Active Substance')],
 [('Biologically Active Substance', 'Pathologic Function'),
  ('Pathologic Function', 'Finding'),
  ('Chemical', 'Biologically Active Substance')],
 [('Pharmacologic Substance', 'Immunologic Factor'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Gene or Genome', 'Biologically Active Substance')],
 [('Pharmacologic Substance', 'Organic Chemical'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Gene or Genome', 'Biologically Active Substance')],
 [('Biologically Active Substance', 'Pathologic Function'),
  ('Pathologic Function', 'Finding'),
  ('Gene or Genome', 'Biologically Active Substance')],
 [('Disease or Syndrome', 'Sign or Symptom'),
  ('Manufactured Object', 'Disease or Syndrome'),
  ('Molecular Biology Research Technique', 'Manufactured Object')],
 [('Disease or Syndrome', 'Patient or Disabled Group'),
  ('Manufactured Object', 'Disease or Syndrome'),
  ('Molecular Biology Research Technique', 'Manufactured Object')],
 [('Disease or Syndrome', 'Age Group'),
  ('Manufactured Object', 'Disease or Syndrome'),
  ('Molecular Biology Research Technique', 'Manufactured Object')],
 [('Disease or Syndrome', 'Finding'),
  ('Manufactured Object', 'Disease or Syndrome'),
  ('Molecular Biology Research Technique', 'Manufactured Object')],
 [('Disease or Syndrome', 'Population Group'),
  ('Manufactured Object', 'Disease or Syndrome'),
  ('Molecular Biology Research Technique', 'Manufactured Object')],
 [('Disease or Syndrome', 'Animal'),
  ('Manufactured Object', 'Disease or Syndrome'),
  ('Molecular Biology Research Technique', 'Manufactured Object')],
 [('Body Part, Organ, or Organ Component', 'Pathologic Function'),
  ('Pathologic Function', 'Finding'),
  ('Nucleic Acid, Nucleoside, or Nucleotide',
   'Body Part, Organ, or Organ Component')],
 [('Pharmacologic Substance', 'Biologically Active Substance'),
  ('Biologically Active Substance', 'Pathologic Function')],
 [('Pharmacologic Substance', 'Immunologic Factor'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Tissue', 'Biologically Active Substance')],
 [('Pharmacologic Substance', 'Organic Chemical'),
  ('Biologically Active Substance', 'Pharmacologic Substance'),
  ('Tissue', 'Biologically Active Substance')],
 [('Biologically Active Substance', 'Pathologic Function'),
  ('Pathologic Function', 'Finding'),
  ('Tissue', 'Biologically Active Substance')]]

需要将每个子列表中的元组重新排序，形成连续链式序列：即前一个元组的第二个元素与后一个元组的第一个元素完全匹配，比如[(a,b), (b,c), (c,d)]。

举个例子：

• 第一个子列表已经符合要求：

  [('Bacterium', 'Biologically Active Substance'),
   ('Biologically Active Substance', 'Pharmacologic Substance'),
   ('Pharmacologic Substance', 'Immunologic Factor')]
  

• 最后一个子列表需要调整顺序：
  原列表：

  [('Biologically Active Substance', 'Pathologic Function'),
   ('Pathologic Function', 'Finding'),
   ('Tissue', 'Biologically Active Substance')]
  

  调整后：

  [('Tissue', 'Biologically Active Substance'),
   ('Biologically Active Substance', 'Pathologic Function'),
   ('Pathologic Function', 'Finding')]
  

注意：子列表长度不固定（可能是2、5或其他数量），元组可替换为列表简化操作。

解决方案 #

核心思路是通过映射关系找到序列的起始节点，再依次串联后续节点，具体实现如下：

Python 实现代码 #

def sort_chain(sub_list):
    # 构建映射：以元素为键，对应以该元素开头的元组/列表
    next_map = {item[0]: item for item in sub_list}
    # 构建前驱映射：以元素为键，对应以该元素结尾的元组/列表
    prev_map = {item[1]: item for item in sub_list}
    
    # 找到序列的起始节点：该节点的第一个元素不存在于前驱映射的键中
    start_item = None
    for item in sub_list:
        if item[0] not in prev_map:
            start_item = item
            break
    
    # 从起始节点开始，依次串联后续节点
    sorted_chain = []
    current = start_item
    while current is not None:
        sorted_chain.append(current)
        # 下一个节点是当前节点第二个元素对应的映射值
        current = next_map.get(current[1])
    
    return sorted_chain

# 批量处理整个嵌套列表
sorted_list = [sort_chain(sub) for sub in list_one]

代码说明 #

1. 映射构建：
   • next_map 记录每个元素作为起始点对应的元组，方便快速查找下一个节点
   • prev_map 记录每个元素作为终点对应的元组，用于定位起始节点
2. 起始节点定位：起始节点的第一个元素不会出现在任何元组的第二个位置（即不在prev_map的键集合中）
3. 序列串联：从起始节点出发，通过next_map依次获取后续节点，直到遍历完所有元素，形成连续链式序列

测试验证 #

用示例中的最后一个子列表测试：

test_sub = [('Biologically Active Substance', 'Pathologic Function'),
            ('Pathologic Function', 'Finding'),
            ('Tissue', 'Biologically Active Substance')]
print(sort_chain(test_sub))
# 输出：
# [('Tissue', 'Biologically Active Substance'), ('Biologically Active Substance', 'Pathologic Function'), ('Pathologic Function', 'Finding')]

该方法适用于任意长度的子列表，只要子列表中的元组确实能组成一条连续的链（题目场景默认满足此条件）。

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