String Replacement Combinations

Question

So I have a string '1xxx1' and I want to replace a certain number (maybe all maybe none) of x's with a character, let's say '5'. I want all possible combinations (...maybe permutations) of the string where x is either substituted or left as x. I would like those results stored in a list.

So the desired result would be

>>> myList = GenerateCombinations('1xxx1', '5')
>>> print myList
['1xxx1','15xx1','155x1','15551','1x5x1','1x551','1xx51']

Obviously I'd like it to be able to handle strings of any length with any amount of x's as well as being able to substitute any number. I've tried using loops and recursion to figure this out to no avail. Any help would be appreciated.

Answer 1

How about:

from itertools import product

def filler(word, from_char, to_char):
    options = [(c,) if c != from_char else (from_char, to_char) for c in word]
    return (''.join(o) for o in product(*options))

which gives

>>> filler("1xxx1", "x", "5")
<generator object <genexpr> at 0x8fa798c>
>>> list(filler("1xxx1", "x", "5"))
['1xxx1', '1xx51', '1x5x1', '1x551', '15xx1', '15x51', '155x1', '15551']

(Note that you seem to be missing 15x51.) Basically, first we make a list of every possible target for each letter in the source word:

>>> word = '1xxx1'
>>> from_char = 'x'
>>> to_char = '5'
>>> [(c,) if c != from_char else (from_char, to_char) for c in word]
[('1',), ('x', '5'), ('x', '5'), ('x', '5'), ('1',)]

And then we use itertools.product to get the Cartesian product of these possibilities and join the results together.

For bonus points, modify to accept a dictionary of replacements. :^)