Как найти все комбинации

Question

Как идти о поиске все комбинации строки и буквы/цифры, например: строка = StackOverflow буква = Z комбинации:

SztackOverFlow 
SztzackOverFlow 
StzackOverFlow 

и так далее .. Я хочу все комбинации.

Другой пример:

строка "Тупой"

буква "Z"

комбинации:

DZumb 
DZuZmb 
DZuZmZb 
DuZmZb 
DumZb 

Я не хочу букву "Z" добавляется в конце или перед строки «Dumb

Я попытался использовать itertools, но я не могу показаться t o ознакомьтесь с их документацией.

Все решения, которые я видел, не то, что я ищу .. он должен производить комбинации я разместил выше ..

Answer 1

Я думаю, что это должно получить, что вы хотите: [Я буду стараться, чтобы оптимизировать это ещё]

def combination(word, letter, start=1, end=-1): 
    if start >= end: 
     return [word] 
    else: 
     new_word = word[:start] + letter + word[start:] 
     output = [new_word, word] 
     output.extend(combination(new_word, letter, start+2, end+1)) 
     output.extend(combination(word, letter, start+1, end)) 
     return list(set(output)) 

выход:

combination('dumb', 'z', start=1, end=len('dumb')) 

['dzuzmb', 'duzmb', 'dzuzmzb', 'dzumb', 'dzumzb', 'dumzb', 'dumb', 'duzmzb'] 

Если вы не хотите, исходное слово в списке возврата, то вы можете пойти с этим кодом:

def combination(word, letter, start=1, end=-1): 
    if start >= end: 
     return [] 
    else: 
     new_word = word[:start] + letter + word[start:] 
     output = [new_word] 
     output.extend(combination(new_word, letter, start+2, end+1)) 
     output.extend(combination(word, letter, start+1, end)) 
     return list(set(output)) 

Объяснение:

база рекурсии заключается в следующем:

if start is >= end: return [No place left to insert letter in word] 

otherwise: 
     insert letter at start of the word and call the same method to work on this new word from inserted index +2. 

     *+2 because say at index 1 in dumb. We insert letter z as dzumd. Now we don't want to insert another z at dzzumb. So +2.* 

     also in the original word just pass it into recursion because we want to work on duzmb. where no z is inserted before u. 

Answer 2

Вот генератор, который использует itertools.product для создания комбинации заполненных и незаполненных слотов, а затем молниеносно их вместе с буквами слово.

from itertools import product 

def inserted(word, ch): 
    n = len(word) - 1 
    last = word[-1] 
    patterns = product(('', ch), repeat=n) 
    # skip the initial empty string pattern 
    next(patterns) 
    for t in patterns: 
     yield ''.join([u+v for u,v in zip(word, t)]) + last 

word = 'Dumb' 
letter = 'Z' 
for s in inserted(word, letter): 
    print(s) 

выход

DumZb 
DuZmb 
DuZmZb 
DZumb 
DZumZb 
DZuZmb 
DZuZmZb 

---

Просто для удовольствия, здесь по существу тот же алгоритм, но с использованием двоичного подсчета вместо itertools.product, поэтому никакого импорта не требуется.

def inserted(word, ch): 
    n = len(word) - 1 
    last = word[-1] 
    t = ('', ch) 
    for i in range(1, 2**n): 
     yield ''.join([u + t[int(b)] 
      for b, u in zip('{:0{}b}'.format(i, n), word)]) + last 

Я думаю, вы согласитесь, что моя первая версия немного легче читать. :)