Python递归：基于字典索引替换句子单词并生成所有排列

Got it, let's break down how to build this recursive function that generates all possible replacement permutations for a sentence. I'll walk you through the logic, code, and key considerations step by step.

The idea is to use backtracking (a recursive technique) to build every possible version of the sentence. For each word in the input, we have two (or more) choices: keep the original word, or use one of its predefined replacements. We recursively explore all these choices, and collect every complete sentence we end up with.

First, let's define our replacement dictionary. Based on your example, it might look like this:

# Predefined replacement dictionary: key = lowercase word, value = list of replacements
REPLACE_DICT = {
    "for": ["4"],
    "to": ["2"],
    "late": ["l8"]
}

Next, the recursive function itself:

def generate_sentence_permutations(input_sentence):
    words = input_sentence.split()
    permutations = set()  # Use a set to automatically avoid duplicate results

    def backtrack(current_index, current_sentence_parts):
        # Base case: we've processed all words, add the complete sentence to results
        if current_index == len(words):
            full_sentence = ' '.join(current_sentence_parts)
            permutations.add(full_sentence)
            return
        
        # Get the current word and its possible options
        current_word = words[current_index]
        lower_case_word = current_word.lower()
        
        # Start with the original word as an option
        possible_options = [current_word]
        # Add replacements if the word exists in our dictionary
        if lower_case_word in REPLACE_DICT:
            possible_options.extend(REPLACE_DICT[lower_case_word])
        
        # Recursively process each option
        for option in possible_options:
            backtrack(current_index + 1, current_sentence_parts + [option])
    
    # Kick off the recursion
    backtrack(0, [])
    return permutations

To test this with your example input:

test_sentence = "For now it is never to late"
results = generate_sentence_permutations(test_sentence)

# Print all results to verify
for sentence in results:
    print(sentence)

• Backtracking Logic: The backtrack function takes two parameters: current_index (which word we're processing next) and current_sentence_parts (the words we've already chosen for the sentence so far). When we reach the end of the word list, we combine the parts into a full sentence and add it to our result set.
• Case Handling: We convert the current word to lowercase to check against the dictionary (so "For" matches "for" in the dict), but we keep the original word as an option to preserve capitalization from the input.
• Duplicate Prevention: Using a set for results ensures we don't get duplicate sentences (useful if multiple words have no replacements, or if replacements could lead to identical sentences).
• Flexibility: You can easily expand the REPLACE_DICT to add more words and multiple replacements per word (e.g., add "never": ["neva", "nvr"] to get even more permutations).

• Punctuation: If your input has punctuation attached to words (like "late!"), you'll need to adjust the word-splitting step. For example, use regex to split words and punctuation separately: import re; words = re.findall(r'\w+|[^\w\s]', input_sentence)
• Case-Sensitive Matches: If you need to only replace exact case matches (e.g., only "For" gets replaced, not "for"), remove the lower() conversion and use the original word as the dictionary key.
• Large Sentences: Python's default recursion depth is more than enough for typical sentences, but if you're working with extremely long text, you could rewrite this using an iterative approach instead.

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