Поиск всех последовательностей A, B таких, которые имеют заданное число каждого элемента

Question

Например, учитывая две буквы A и B, я хотел бы сгенерировать все строки длины n, имеющие x A и y B.

Хотелось бы, чтобы это было сделано эффективно. Один из способов, который я рассмотрел, - построить список x списка A, а затем вставить y B в список каждый возможный путь. Но вставка в список python является линейной, поэтому этот метод будет сосать по мере того, как список станет большим.

ЦЕЛЬ ПРОИЗВОДИТЕЛЬНОСТИ (это может быть необоснованным, но это is моя надежда): Генерировать все строки длины 20 с равными числами A и B через минуту меньше минуты.

EDIT: Предлагаются перестановки ('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 «s (называя его 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))