查找A，B的所有序列，使每個元素具有指定數量

Question

例如，給定兩個字母A和B，我想要生成所有具有x A和y B的長度爲n的字符串。

我想這樣做是有效的。我考慮的一種方法是構建A的長度爲x的列表，然後以可能的方式將y B插入列表中。但插入python列表是線性的，所以這個方法會吸收，因爲列表變得很大。

績效目標（這可能是不合理的，但它是我希望）：生成具有相等數量和B長度爲20的所有字符串的時間不到一分鐘。

編輯：使用排列（'A'* x，'B'* y）已被建議。雖然不是一個壞主意，但是它浪費了很多。如果x = y = 4，則會多次生成字符串「AAAABBBB」。有沒有更好的方法可能會產生每個字符串只有一次？我試過代碼的效果（排列（'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))