Python递归生成同义句：如何避免重复用词并管理状态？

通过递归函数结合正则匹配生成文本，正则模式pattern = '\[.*?\]'用于匹配方括号内的同义词组合，同义词间由自定义分隔符SEPARATOR =#lkmkmksdmf###分隔。目标是生成所有可能的句子组合，但要求同一句子中不能重复使用相同单词。

初始输入句子示例：

[decreasing#lkmkmksdmf###shrinking#lkmkmksdmf###falling#lkmkmksdmf###contracting#lkmkmksdmf###faltering#lkmkmksdmf###the contraction in] exports of services will drive national economy to a 0.3% real GDP [decline#lkmkmksdmf###decrease#lkmkmksdmf###contraction] in 2023 from an estimated 5.0% [decline#lkmkmksdmf###decrease#lkmkmksdmf###contraction] in 2022

现有DFS递归函数可生成句子并存入master_sentence_list，但无法避免重复单词问题。尝试添加avoid_words参数记录已用单词，但不知如何在分支切换时回溯清除该列表，需修改函数实现需求。

现有递归函数代码：

def combinations(self,sentence,master_sentence_list:list):
        pattern = '\[.*?\]'

        if not re.findall(pattern, sentence, flags = re.IGNORECASE):
            if sentence not in master_sentence_list:  # 修正原代码的变量名拼写错误
                master_sentence_list.append(sentence)
        else:
            for regex_match in re.finditer(pattern, sentence, flags = re.IGNORECASE):
                repl=regex_match.group(0)[1:-1]
                start_span = regex_match.span()[0]
                end_span = regex_match.span()[1]
                for word in repl.split(self.SEPARATOR):
                    tmpsentence = (
                        sentence[0: start_span] +
                        word +
                        sentence[end_span:]
                    )
                    new_sentence = deepcopy(tmpsentence)
                    self.combinations(new_sentence,master_sentence_list)

核心思路是通过传递列表副本实现回溯：每次递归时创建新的已用单词列表，而非共享同一个可变列表，这样不同分支的已用单词记录不会互相干扰。具体修改如下：

修改后的完整代码 #

import re
from copy import deepcopy

def combinations(self, sentence, master_sentence_list: list, avoid_words: list = None):
    # 初始化默认参数，规避Python默认可变参数的共享陷阱
    if avoid_words is None:
        avoid_words = []
    
    pattern = r'\[.*?\]'
    matches = re.findall(pattern, sentence, flags=re.IGNORECASE)
    
    if not matches:
        # 无待替换项时，检查句子是否重复，不重复则存入列表
        if sentence not in master_sentence_list:
            master_sentence_list.append(sentence)
        return
    
    # 每次只处理第一个未替换的方括号组，符合DFS逻辑
    regex_match = next(re.finditer(pattern, sentence, flags=re.IGNORECASE))
    repl = regex_match.group(0)[1:-1]
    start_span, end_span = regex_match.span()
    
    for word in repl.split(self.SEPARATOR):
        # 跳过已使用过的单词
        if word in avoid_words:
            continue
        
        # 生成替换后的新句子
        tmpsentence = sentence[:start_span] + word + sentence[end_span:]
        new_sentence = deepcopy(tmpsentence)
        
        # 递归调用时传递新的已用单词列表（原列表+当前单词），自动实现回溯
        self.combinations(new_sentence, master_sentence_list, avoid_words + [word])

关键说明 #

1. 回溯实现：每次递归传递avoid_words + [word]会创建新列表，原分支的已用单词记录不会被修改，递归返回时自动回到上一分支的状态，无需手动清除；
2. 避免重复替换：改为每次只处理第一个匹配的方括号组，防止原代码中循环处理所有匹配项导致的重复生成问题；
3. 默认参数安全：添加avoid_words is None的初始化逻辑，避免多次调用函数时共享同一个默认列表。

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