基于打乱二元组生成同长度可行句子的Python算法需求

问题背景 #

你提到的场景很清晰：给定一个原句子对应的二元组袋（bag-of-bigrams）——也就是原句子中所有连续两个元素的无序集合（但保留重复次数），我们需要找出所有和原句子长度相同的可行句子排列。比如原句子ABCABA对应的二元组袋是{(AB), (BC), (CA), (AB), (BA)}，我们要找出所有符合这个二元组组合的6元素句子。

针对你给出的输入示例：

[ ('t','h'), ('h','e'), ('e', ' '), (' ','f') , ('f','o'), ('o','x'), ('x',' '), (' ','a'), ('a','t'), ('t','e'), ('e', '<p>') ]

这个二元组袋对应的唯一可行句子应该是the fox ate<p>，我们的算法会准确还原它（如果有多个可能的句子，也会全部列出）。

核心思路 #

这个问题本质上是在有向图中寻找所有欧拉路径：

• 把每个元素（字符/词）看作图的节点
• 每个二元组(u, v)看作从u到v的一条有向边，重复的二元组对应多条相同的边
• 原句子就是一条遍历所有边恰好一次的欧拉路径，路径上的节点拼接起来就是句子，节点数量正好是边数+1（也就是原句子的长度）

代码实现 #

下面是完整的Python代码，包含注释和测试用例：

from collections import defaultdict, Counter

def generate_possible_sentences(bigrams):
    # 统计每个二元组的出现次数，避免重复处理
    bigram_counts = Counter(bigrams)
    # 构建带计数的邻接表：key是起始节点，value是{目标节点: 剩余可用边数}
    adjacency = defaultdict(dict)
    # 统计每个节点的入度和出度，用于确定欧拉路径的起点
    in_degree = defaultdict(int)
    out_degree = defaultdict(int)
    
    for (start_node, end_node), count in bigram_counts.items():
        adjacency[start_node][end_node] = count
        out_degree[start_node] += count
        in_degree[end_node] += count
    
    # 确定所有可能的起始节点（遵循欧拉路径的规则）
    start_candidates = []
    # 情况1：存在一个节点出度比入度多1（欧拉路径的起点）
    for node in set(out_degree.keys()).union(in_degree.keys()):
        if out_degree[node] == in_degree[node] + 1:
            start_candidates.append(node)
    # 情况2：所有节点入度等于出度（欧拉回路，任意节点都可作为起点）
    if not start_candidates:
        for node in set(out_degree.keys()).union(in_degree.keys()):
            if out_degree[node] == in_degree[node]:
                start_candidates.append(node)
        # 处理空输入的特殊情况
        if not start_candidates and len(bigram_counts) == 0:
            return []
    
    all_valid_sentences = []
    total_edges = sum(bigram_counts.values())  # 总边数=二元组的数量
    
    # 回溯函数：遍历所有可能的欧拉路径
    def backtrack(current_node, current_path, edges_used):
        # 当所有边都被使用时，当前路径就是一个有效句子
        if edges_used == total_edges:
            all_valid_sentences.append(''.join(current_path))
            return
        # 遍历当前节点的所有邻接节点
        for neighbor in list(adjacency[current_node].keys()):
            if adjacency[current_node][neighbor] > 0:
                # 使用这条边，减少可用次数
                adjacency[current_node][neighbor] -= 1
                # 继续回溯，路径添加邻接节点，已用边数+1
                backtrack(neighbor, current_path + [neighbor], edges_used + 1)
                # 回溯：恢复边的可用次数
                adjacency[current_node][neighbor] += 1
    
    # 对每个候选起点执行回溯
    for start in start_candidates:
        backtrack(start, [start], 0)
    
    return all_valid_sentences

# 测试你给出的输入示例
input_bigrams = [ ('t','h'), ('h','e'), ('e', ' '), (' ','f') , ('f','o'), ('o','x'), ('x',' '), (' ','a'), ('a','t'), ('t','e'), ('e', '<p>') ]
result = generate_possible_sentences(input_bigrams)
print("所有可行句子：")
for sentence in result:
    print(f"- {sentence}")

代码说明 #

1. 统计与图构建：用Counter统计二元组的重复次数，然后构建带边计数的邻接表，同时统计每个节点的入度和出度。
2. 起点确定：根据欧拉路径的定理筛选起点：要么是出度比入度多1的节点，要么是所有节点入度出度相等时的任意节点。
3. 回溯遍历：通过回溯法尝试所有可能的路径，每次使用一条边就减少其可用次数，回溯时恢复，直到用完全部边，此时的路径就是有效句子。
4. 结果拼接：把路径上的节点直接拼接（如果是词的话，可以改成' '.join(current_path)）得到最终句子。

注意事项 #

• 如果输入的二元组袋无法形成有效句子（比如不存在欧拉路径），函数会返回空列表。
• 当存在多个可行句子时，函数会全部列出（比如原示例ABCABA对应的二元组袋，会输出所有符合条件的排列）。
• 支持元素为词的场景：只需把输入中的字符换成词，修改拼接逻辑即可。

内容的提问来源于stack exchange，提问作者D. Rad