python之查找 A、B 的所有序列，使得每个元素具有指定数量

例如，给定两个字母 A 和 B，我想生成所有长度为 n 且具有 x 个 A 和 y 个 B 的字符串。

我希望这能高效地完成。我考虑过的一种方法是构建一个长度为 x 的 A 列表，然后以各种可能的方式将 y B 插入列表中。但是插入 Python 列表是线性的，所以随着列表变大，这种方法会很糟糕。

性能目标(这可能不合理，但是我的希望):在不到一分钟的时间内生成所有长度为 20、A 和 B 数量相等的字符串。

编辑:建议使用排列('A' * x, 'B' * y)。虽然不是一个坏主意，但它浪费了很多。如果 x = y = 4，您将多次生成字符串 'AAAABBBB'。有没有更好的方法可以只生成每个字符串一次？我已经尝试过代码来达到 set(permutations('A' * x, 'B' * y)) 的效果，但它太慢了。

请您参考如下方法:

关于您对性能的担忧，这里是您想法的实际生成器实现(没有insert)。它找到 B 的位置并相应地填充列表。

import itertools 
 
def make_sequences(num_a, num_b): 
    b_locations = range(num_a+1) 
    for b_comb in itertools.combinations_with_replacement(b_locations, num_b): 
        result = [] 
        result_a = 0 
        for b_position in b_comb: 
            while b_position > result_a: 
                result.append('A') 
                result_a += 1 
            result.append('B') 
        while result_a < num_a: 
            result.append('A') 
            result_a += 1 
        yield ''.join(result) 

它确实表现更好。与 Greg Hewgill 相比的解决方案(将其命名为 make_sequences2):

In : %timeit list(make_sequences(4,4)) 
10000 loops, best of 3: 145 us per loop 
 
In : %timeit make_sequences2(4,4) 
100 loops, best of 3: 6.08 ms per loop 

编辑

通用版本:

import itertools 
 
def insert_letters(sequence, rest): 
    if not rest: 
        yield sequence 
    else: 
        letter, number = rest[0] 
        rest = rest[1:] 
        possible_locations = range(len(sequence)+1) 
        for locations in itertools.combinations_with_replacement(possible_locations, number): 
            result = [] 
            count = 0 
            temp_sequence = sequence 
            for location in locations: 
                while location > count: 
                    result.append(temp_sequence[0]) 
                    temp_sequence = temp_sequence[1:] 
                    count += 1 
                result.append(letter) 
            if temp_sequence: 
                result.append(temp_sequence) 
            for item in insert_letters(''.join(result), rest): 
                yield item 
 
def generate_sequences(*args): 
    ''' 
    arguments : squence of (letter, number) tuples 
    ''' 
    (letter, number), rest = args[0], args[1:] 
    for sequence in insert_letters(letter*number, rest): 
        yield sequence 

用法:

for seq in generate_sequences(('A', 2), ('B', 1), ('C', 1)): 
    print seq 
 
# Outputs 
#  
# CBAA 
# BCAA 
# BACA 
# BAAC 
# CABA 
# ACBA 
# ABCA 
# ABAC 
# CAAB 
# ACAB 
# AACB 
# AABC