如何实现类似n-gram的字符串片段顺序选取？求正确实现方案

Hey there! Let's work through this problem to get the exact output you're looking for. First, let's break down what you need: given a string of space-separated words, you want a list of all non-empty ordered word combinations (preserving the original word order) in the specific sequence shown in your example.

What's wrong with your current code? #

Your existing code has two immediate issues that prevent it from running, plus a logical gap:

• The variable n is undefined, so the list comprehension will throw a NameError.
• input_list isn't defined either, so the extend() call will also fail.
• Most importantly, your approach only generates consecutive word substrings (like jan feb or feb mar), but your requirement includes non-consecutive combinations (like jan mar).

The Correct Solution #

We'll use a backtracking approach to generate all valid non-empty subsets of words (keeping their original order), then sort the results to match the sequence in your example. Here's the code:

def generate_word_combinations(my_string):
    words = my_string.split()
    combinations = []
    word_index = {word: idx for idx, word in enumerate(words)}

    # Backtrack to generate all non-empty ordered subsets
    def backtrack(start, current_path):
        if current_path:
            # Store the combination string plus metadata for sorting
            combo_str = ' '.join(current_path)
            combinations.append((
                combo_str,
                word_index[current_path[0]],  # Index of first word
                len(current_path),            # Length of combination
                word_index[current_path[-1]]  # Index of last word
            ))
        for i in range(start, len(words)):
            backtrack(i + 1, current_path + [words[i]])

    backtrack(0, [])

    # Sort to match your desired sequence:
    # 1. Order by the position of the first word in the original list
    # 2. Then by combination length (shorter first)
    # 3. Finally by the position of the last word (earlier first)
    combinations.sort(key=lambda x: (x[1], x[2], x[3]))

    # Extract just the combination strings
    return [combo[0] for combo in combinations]

# Test it with your example
my_string = "jan feb mar"
print(generate_word_combinations(my_string))
# Output: ['jan', 'jan feb', 'jan mar', 'jan feb mar', 'feb', 'feb mar', 'mar']

How This Works #

1. Split the Input: First, we split the input string into a list of individual words.
2. Backtracking for Subsets: The backtrack function recursively builds all possible non-empty subsets of words, ensuring we only add words that come after the current one (to preserve order). We store each subset along with metadata to help sort later.
3. Sorting to Match Your Sequence: We sort the combinations first by the position of their first word (so all jan combinations come before feb ones), then by length (shorter combinations first), and finally by the position of the last word (so jan feb comes before jan mar).
4. Extract Results: We strip out the metadata and return just the formatted combination strings.

Why This Works for Your Example #

This approach covers all required combinations—including non-consecutive ones like jan mar—and sorts them exactly into the order you specified in your sample output.

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