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

Please explain what you mean by those combinations. How you want them to form. Help us help you. — Vikash Singh, Jan 24 '17 at 03:27
@user2357112 How can I explain anymore lol? homework sheet? I need it to produce all combinations.. so for examples lets say I want the string "Dumb" and I want another letter "Z": all combinations: DZumb DZuZmb DZuZmZb DuZmZb DumZb better explanation now? only one thing to add... I dont want the letter "Z" added to the end or front of the string "Dumb". — PythonNLMB, Jan 24 '17 at 03:28
Nope, still not enough. You have some nonstandard definition of "combination" in mind that you have not properly conveyed. Simply saying the word "combination" won't convey the definition you have in your head. While examples help, they are no substitute for an actual definition, especially since your example has some oddities that suggest that you got it wrong. — user2357112, Jan 24 '17 at 03:34
OK. So there are 3 slots in "Dumb" where "Z" can be inserted. That means there are `2**3=8` possible combinations. — PM 2Ring, Jan 24 '17 at 03:35
@PM2Ring Thank you for an actual response. Yes you are correct. and stack over flow is 2**12 = 4096 combinations. Now how would I go about creating a script in python that presents me all those combinations? — PythonNLMB, Jan 24 '17 at 03:43
I'm reopening this question, not because I don't think it's probably a duplicate of a previous question, but because I don't think the dup target was very good -- there's a (tiny) bit more to this question than just knowing about itertools.product, and there are much better Cartesian product question targets if we really want to do that. — DSM, Jan 24 '17 at 03:57

PM 2Ring · Answer 1 · 2017-01-24T04:09:24.287

Here's a generator that uses itertools.product to create the combinations of filled and unfilled slots and then zips them together with the letters of the word.

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)

output

DumZb
DuZmb
DuZmZb
DZumb
DZumZb
DZuZmb
DZuZmZb

Just for fun, here's essentially the same algorithm, but using binary counting instead of itertools.product, so no imports are required.

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

I think you'll agree that my first version is a little easier to read. :)

I was playing around with `[''.join(chain(*zip(word, p + ("",)))) for p in product(["","Z"], repeat=len(word)-1)]`.. — DSM, Jan 24 '17 at 03:52
@DSM Nice, and I guess it's not a big deal that it also includes the original word. — PM 2Ring, Jan 24 '17 at 03:58

Vikash Singh · Accepted Answer · 2017-01-24T03:53:52.323

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.

How to find all combinations

2 Answers2