Список всех возможных строк из заданных возможностей для символов

Question

Может быть, слишком рано утром для рекурсии, но у меня непомерное количество проблем, связанных с правильным алгоритмом для этого.

У меня есть такая строка: abcd

За исключением того, что я не совсем уверен во всех его письмах. Возможно, что a на самом деле должен быть A или, может быть, даже @. d может быть d или D или даже +. Итак, я придумал это:

possibilities = [['a', 'A', '@'], 'bc', ['d', 'D', '+']]

Я хочу составить список всех возможных слов, которые могут быть:

output = [
    'abcd',
    'Abcd',
    '@bcd',
    'abcD',
    # etc.
]

Порядок этого списка не имеет значения для меня.

Я взглянул на itertools, но с первого взгляда не смог найти функцию, которая подходила бы мне, поэтому я решил реализовать рекурсивное решение.

def find_possible_strings(possibilities):
  res = []
  f2(possibilities, '', res)
  return res

def f2(possibilities, s, final_result):
  for i,elem in enumerate(possibilities):
    if type(elem) == str:
      s += elem
    else:
      for e in elem:
        f2(possibilities[i+1:], s + e, final_result)

  final_result.append(s)

possibilities = [['a', 'A', '@'], 'bc', ['d', 'D', '+']]
print '\n'.join(find_possible_strings(possibilities))

Прямо сейчас печатается:

abcd
abcD
abc+
abc
Abcd
AbcD
Abc+
Abc
@bcd
@bcD
@bc+
@bc
bcd
bcD
bc+
bc

Полагаю, я получаю все возможные строки, которые хочу, но также и кучу неполных строк. Думаю, проблема в том, что я не добавляю к s в блоке else, поэтому добавление s I в конце функции является неполным.

Если в конце функции запретить использование кода типа if len(s) != 4: return, как мне исправить эту функцию?

Вы можете изменить входные и выходные структуры данных, если другая более подходит. Конечно, вы можете заменить мою функцию вызовом библиотеки, если это упростит задачу.

Тем временем я еще немного поработаю.

Answer 1

Это не проблема рекурсивной формы, поэтому опустите этот молот.

Вы генерируете декартово произведение из 4 списков возможностей, по одному на каждую позицию. Используйте itertools.product() (и присвойте каждой позиции свой список), и все готово:

from itertools import product

possibilities = [['a', 'A', '@'], ['b'], ['c'], ['d', 'D', '+']]

for combo in product(*possibilities):
    print(''.join(combo))

Демо-версия:

>>> from itertools import product
>>> possibilities = [['a', 'A', '@'], ['b'], ['c'], ['d', 'D', '+']]
>>> for combo in product(*possibilities):
...     print(''.join(combo))
...
abcd
abcD
abc+
Abcd
AbcD
Abc+
@bcd
@bcD
@bc+