基于相邻数值关联生成四字符序列的脚本实现方法问询

这个问题本质上可以转化为图的哈密顿路径查找问题——把每个数字看作图的节点，输入的相邻数字对就是连接节点的无向边，我们要找的就是包含全部4个节点的完整路径（也就是长度为4的字符序列）。下面是具体的程序化实现思路：

1. 先构建邻接表（表示图的结构） #

首先需要把输入的相邻对转换成计算机容易处理的图结构，这里用邻接表（字典结构最方便）：

• 遍历每一个输入的数字对，把它拆成两个独立节点，比如输入"42"就拆成'4'和'2'
• 因为是无向边（4和2相邻等价于2和4相邻），所以要在邻接表中给两个节点互相添加对方作为邻接点
• 举个例子，输入['42','23','14']对应的邻接表是：

  adjacency = {
      '4': ['2', '1'],
      '2': ['4', '3'],
      '3': ['2'],
      '1': ['4']
  }
  

2. 用深度优先搜索（DFS）遍历所有可能的哈密顿路径 #

我们需要找到包含所有4个节点的路径，所以用DFS来递归探索所有可能的路径分支：

• 遍历1、2、3、4每个数字作为起始节点，尝试从每个节点出发构建路径
• 递归过程中做这些操作：
  • 如果当前路径的长度已经是4（包含所有节点），就把这个路径加入结果列表
  • 遍历当前节点的所有邻接点，如果邻接点还没在当前路径里，就把它加入路径，继续递归探索
  • 递归结束后回溯：把当前节点从路径中移除，尝试其他邻接点的分支

3. 结果去重与输出 #

• 因为图是无向的，可能会生成反向的路径（比如1423和3241），这两个都是符合要求的有效序列，如果不需要去重可以直接保留；如果需要唯一结果，可以用集合去重后再转回列表
• 最后输出所有符合条件的四字符序列

代码示例（Python） #

下面是一个可运行的简单实现，你可以直接测试：

def generate_valid_sequences(input_pairs):
    # 第一步：构建邻接表
    adj = {}
    for pair in input_pairs:
        node1, node2 = pair[0], pair[1]
        # 给node1添加邻接点
        if node1 not in adj:
            adj[node1] = []
        adj[node1].append(node2)
        # 给node2添加邻接点（无向边）
        if node2 not in adj:
            adj[node2] = []
        adj[node2].append(node1)
    
    valid_sequences = []
    
    # 第二步：DFS遍历所有可能的路径
    def dfs(current_node, current_path):
        # 路径长度达到4，说明找到有效序列
        if len(current_path) == 4:
            valid_sequences.append(''.join(current_path))
            return
        # 遍历当前节点的所有邻接点
        for neighbor in adj[current_node]:
            if neighbor not in current_path:
                # 递归探索，把邻接点加入路径
                dfs(neighbor, current_path + [neighbor])
    
    # 遍历所有起始节点
    for start_node in adj.keys():
        dfs(start_node, [start_node])
    
    # 去重（可选，根据需求决定是否保留反向路径）
    unique_sequences = list(set(valid_sequences))
    return unique_sequences

# 测试用例
test_input = ['42', '23', '14']
print(generate_valid_sequences(test_input))
# 输出：['1423', '3241']

内容的提问来源于stack exchange，提问作者S.Haran