Python中从动态生成多列表查找连续数的实现方案（含短语搜索场景）

Core Function Implementation #

First, let's write a function that checks if there's a consecutive sequence across any number of input lists. The key idea is to track possible values at each step, narrowing down to only values that are exactly one more than a value from the previous list.

def has_consecutive_sequence(lists):
    # Handle edge cases: no lists or any empty list
    if not lists:
        return False
    for lst in lists:
        if not lst:
            return False
    
    # Convert lists to sets for fast membership checks
    value_sets = [set(lst) for lst in lists]
    
    # Start with all values from the first list
    possible_values = value_sets[0].copy()
    
    # Iterate through each subsequent list
    for current_set in value_sets[1:]:
        next_possible = set()
        # Check if any value from the previous step can be extended by 1
        for num in possible_values:
            if (num + 1) in current_set:
                next_possible.add(num + 1)
        
        # If no valid next values exist, sequence is impossible
        if not next_possible:
            return False
        
        possible_values = next_possible
    
    # If we made it through all lists, a valid sequence exists
    return True

How It Works #

1. Edge Case Handling: First, we check if there are no lists, or if any list is empty (since we can't pick an element from an empty list).
2. Set Conversion: Converting each list to a set makes checking if a number exists much faster (O(1) time vs O(n) for lists).
3. Tracking Possible Values: We start with all values from the first list. For each next list, we only keep values that are exactly previous_value + 1 (since we need consecutive numbers).
4. Early Exit: If at any point there are no valid next values, we immediately return False—no need to check further.

Applying to Phrase Search #

To use this for your phrase search task, we need to:

1. Extract the position lists in the order of the phrase words.
2. Pass these lists to the has_consecutive_sequence function.

Here's a helper function for this:

def phrase_exists(position_dict, phrase):
    # Get position lists in the order of the phrase
    try:
        phrase_position_lists = [position_dict[word] for word in phrase]
    except KeyError:
        # A word in the phrase isn't present in the sentence
        return False
    
    # Check if there's a consecutive sequence of positions
    return has_consecutive_sequence(phrase_position_lists)

Example Usage #

Let's test this with your sample data:

# Sample position dictionary from the sentence "My friend is my colleague."
pos_dict = {
    'My': [0, 3],
    'friend': [1],
    'is': [2],
    'colleague': [4]
}

# Check if "friend is my" exists (note: using 'My' as per the dict keys)
print(phrase_exists(pos_dict, ["friend", "is", "My"]))  # Output: True

# Check if "My is friend" exists
print(phrase_exists(pos_dict, ["My", "is", "friend"]))  # Output: False

# Check single-word phrase
print(phrase_exists(pos_dict, ["colleague"]))  # Output: True

Explanation for Phrase Search #

• The phrase_exists function first gets the position lists for each word in the phrase, in the same order. If any word isn't in the position dictionary, it returns False immediately.
• It then uses the core function to check if there's a sequence of positions where each next position is exactly one more than the previous (meaning the words appear consecutively in the sentence).

Key Notes for Beginners #

• Set Efficiency: Using sets is crucial for performance, especially if your position lists are large. Without sets, checking membership in lists would slow down the function significantly.
• Order Matters: The lists must be passed in the exact order of the phrase—since we're looking for consecutive positions in the sentence, the order of the words (and their position lists) is critical.
• Edge Cases: The function handles empty lists, missing words, and single-word phrases automatically, which covers most real-world scenarios for phrase search.

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