如何生成满足字符重复限制的2ⁿ个不等长字符序列？

Got it, let's break this down step by step. Here's how you can build this function, along with flexible ways to add the restrictions you mentioned.

The core idea maps directly to your binary analogy: each character in the input word has two choices (repeat once = binary 0, repeat twice = binary 1). With n characters, we get exactly 2ⁿ unique sequences.

Step 1: Base Sequence Generator #

Here's a Python implementation that generates all valid sequences using itertools to handle the binary combinations efficiently:

import itertools

def generate_char_sequences(word):
    n = len(word)
    # Generate all n-length binary combinations (0 = 1 repeat, 1 = 2 repeats)
    binary_options = itertools.product([0, 1], repeat=n)
    sequences = []
    
    for combo in binary_options:
        current_seq = ""
        for char, repeat_flag in zip(word, combo):
            # Multiply character by 1 or 2 based on the binary flag
            current_seq += char * (1 + repeat_flag)
        sequences.append(current_seq)
    
    return sequences

How it works: #

• itertools.product([0,1], repeat=n) creates every possible n-bit binary pattern (e.g., for n=3: (0,0,0), (0,0,1), ..., (1,1,1)).
• For each pattern, we iterate through the input word, appending each character once or twice based on the corresponding binary digit.
• The result is a list of 2ⁿ unique sequences (assuming no duplicate characters in the input word).

Step 2: Adding Custom Restrictions #

You mentioned needing to restrict the generated results—here are common tweaks you can adapt based on your specific needs:

Example 1: Remove Duplicate Sequences #

If your input word has repeated characters, some combinations might produce identical sequences. Use a set to auto-deduplicate:

def generate_deduplicated_sequences(word):
    n = len(word)
    binary_options = itertools.product([0, 1], repeat=n)
    unique_sequences = set()
    
    for combo in binary_options:
        current_seq = ""
        for char, repeat_flag in zip(word, combo):
            current_seq += char * (1 + repeat_flag)
        unique_sequences.add(current_seq)
    
    return list(unique_sequences)

Example 2: Filter by Sequence Length #

If you only want sequences within a specific length range:

def generate_length_restricted_sequences(word, min_len, max_len):
    n = len(word)
    binary_options = itertools.product([0, 1], repeat=n)
    filtered_sequences = []
    
    for combo in binary_options:
        current_seq = ""
        for char, repeat_flag in zip(word, combo):
            current_seq += char * (1 + repeat_flag)
        if min_len <= len(current_seq) <= max_len:
            filtered_sequences.append(current_seq)
    
    return filtered_sequences

Example 3: Exclude Specific Substrings #

To reject sequences containing unwanted patterns (e.g., three consecutive identical characters, though our base logic prevents this by design):

def generate_filtered_sequences(word, forbidden_substrings):
    n = len(word)
    binary_options = itertools.product([0, 1], repeat=n)
    valid_sequences = []
    
    for combo in binary_options:
        current_seq = ""
        for char, repeat_flag in zip(word, combo):
            current_seq += char * (1 + repeat_flag)
        # Check if any forbidden substring exists
        if not any(sub in current_seq for sub in forbidden_substrings):
            valid_sequences.append(current_seq)
    
    return valid_sequences

Test the base function with a sample input:

# Test with word "abc" (3 characters = 8 sequences)
result = generate_char_sequences("abc")
print(len(result))  # Output: 8
print(result)
# ['abc', 'abbc', 'abcc', 'abbcc', 'aabc', 'aabbc', 'aabcc', 'aabbcc']

# Test deduplication with word "aab"
dedupe_result = generate_deduplicated_sequences("aab")
print(len(dedupe_result))  # Output: 6 (2 duplicates removed)

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