查找A，B的所有序列，这些序列具有指定数目的每个元素

Question

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

我希望这件事能有效地进行。我考虑过的一种方法是建立A的长度x列表，然后将y插入到列表中，所有可能的方式。但是插入python列表是线性的，所以当列表变大时，这个方法会很糟糕。

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

编辑:使用置换(‘A’* x，'B‘* y)已被建议。虽然这主意不错，但却浪费了很多时间。如果x=y= 4，则会多次生成字符串'AAAABBBB‘。是否有更好的方法只生成每个字符串一次？我尝试过使用set(置换(‘A’* x，'B‘* y))的效果，它太慢了。

Answer 1

关于您对性能的关注，下面是您的想法的实际生成器实现(没有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

Answer 2

要做到这一点，一个简单的方法是：

import itertools

def make_sequences(x, y):
    return set(itertools.permutations("A" * x + "B" * y))

itertools.permutations()函数没有考虑输入列表中的重复元素。它最终产生的排列是以前生成的排列的重复。因此，使用set()构造函数移除结果中的重复元素。

Answer 3

这应该会给你一个想法(我已经把每一个步骤都包括了，这样你就可以看到发生了什么)：

>>> x = 2
>>> y = 3
>>> lst_a = ['A'] * x
>>> lst_b = ['B'] * y
>>> print lst_a, lst_b
['A', 'A'] ['B', 'B', 'B']
>>> lst_a.extend(lst_b)
>>> lst_a
['A', 'A', 'B', 'B', 'B']
>>> print list(itertools.permutations(lst_a))