Replacing chars in a string in every way

Question

I'm looking for help on a function that takes a string, and replaces every character in that string in every way. I'm not quite sure how to word my question so that it makes sense so I'll show you what it's supposed to do.

stars('1')
returns ['*']

stars('12')
returns ['*1', '1*', '**']

stars('123')
returns ['*23', '1*3', '12*', '**3', '*2*', '**1', '***']

stars('1234')
returns ['*234', '1*34', '12*4', '123*', '**34', '*2*4', '*23*', '1**4', '1*3*', 
         '12**', '***4', '**3*', '*2**', '1***', '****']

Did that all out by hand, but even if I made a mistake, you should get the idea of what I'm looking for now. The final case (all *'s) isn't required but I put it in there to make sure the problem was understood.

Here is what I've come up with so far but it doesn't quite work.

def stars(n):
    lst = []
    length = len(n)
    for j in xrange(0, length):
        p = list(n)
        for k in xrange(j, length):
            p[k] = '*'
            lst += [''.join(p)]
    return lst

Output:

'1' returns ['*']
'12' returns ['*2', '**', '1*']
'123' returns ['*23', '**3', '***', '1*3', '1**', '12*']
'1234' returns ['*234', '**34', '***4', '****', '1*34', '1**4', '1***', '12*4', '12**', '123*']

Any help would be greatly appreciated. Would like this answered in Python if possible, but if you don't know Python, then pseudocode or another language would be acceptable. If it's written clearly, I'm sure I could convert it into Python on my own.

Answer 1

I think the canonical approach in Python would be to use the itertools module:

>>> from itertools import product, cycle
>>> s = 'abcde'
>>> [''.join(chars) for chars in product(*zip(s, cycle('*')))]
['abcde', 'abcd*', 'abc*e', 'abc**', 'ab*de', 'ab*d*', 'ab**e', 'ab***', 
 'a*cde', 'a*cd*', 'a*c*e', 'a*c**', 'a**de', 'a**d*', 'a***e', 'a****', 
 '*bcde', '*bcd*', '*bc*e', '*bc**', '*b*de', '*b*d*', '*b**e', '*b***',
 '**cde', '**cd*', '**c*e', '**c**', '***de', '***d*', '****e', '*****']

and then you could just toss the first one without any stars, but that might seem a little magical.

ISTM you have two other approaches if you don't want to use the built-in Cartesian product function: you can use recursion, or you can take advantage of the fact that you want to turn each star on and off, a binary switch. That means with n letters you'll have 2^n (-1, if you remove the no-star case) possibilities to return, and whether or not to put a star somewhere corresponds to whether or not the corresponding bit in the number is set (e.g. for 'abc' you'd loop from 1 to 7 inclusive, 1 = 001 so you'd put a star in the last place, 7 = 111 so you'd put a star everywhere, etc.)

This last one is pretty simple to implement, so I'll leave that for you. :^)