How to find all combinations

Question

How do I go about finding all combinations of a string and a letter/number for example: string = StackOverFlow letter = Z combinations:

SztackOverFlow
SztzackOverFlow
StzackOverFlow

and so on... I want all the combinations.

Another example:

string "Dumb"

letter "Z"

combinations:

DZumb
DZuZmb
DZuZmZb
DuZmZb
DumZb 

I dont want the letter "Z" added to the end or front of the string "Dumb

I have tried using itertools, but I cant seem to figure it out with their documentation.

All the solutions I have seen are not what I am looking for.. it needs to produce the combinations i posted above..

Answer 1

I think this should get you what you want: [I will try to optimise it more]

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))

output:

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

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

If you don't want the original word in the return list then you can go with this code:

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))

Explanation:

base of recursion is this:

 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.