Replacing characters in a string in every way

Question

I am looking for help for a function that takes a string, and in every way replaces every character in that string. I'm not quite sure how to formulate my question so that it makes sense, so I will show you what it should 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***', '****'] 

I did it all manually, but even if I made a mistake, you should get an idea of ​​what I'm looking for now. The final case (all *) is not required, but I put it there to make sure the problem is understood.

Here is what I came up with so far, but it does not 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. If possible, respond to Python, but if you don't know Python, then pseudo-code or another language would be acceptable. If it's written clearly, I'm sure I can convert it to Python myself.

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 can just throw the first without stars, but it may seem a little magical.

ISTM you have two other approaches if you do not want to use the built-in Cartesian function of the product: you can use recursion, or you can take advantage of the fact that you want to enable or disable each star binary switch. This means that with the characters n you will have 2 ^ n (-1 if you delete the case without a star) the opportunity to return, and whether to put the star somewhere, does the corresponding bit in the number set (for example, for 'abc' you will do a cycle from 1 to 7 inclusive, 1 = 001, so that you put the star in last place, 7 = 111, so that you hang the star everywhere, etc.)

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

Answer 2

You can see this as a problem of finding and repeating all subsequences of characters in the original string. (For each subsequence, replace the characters in it with "*", and leave the rest alone).

For a given subsequence, each character is either in it or not, so for an N-character string there are 2 ^ N subsequences. Probably the easiest way to enumerate them is to iterate over integers from 0 to (2 ^ N) -1 and use their binary representations as signs of whether to replace the character or not

With N = 3, it looks like this:

 0 000 abc 1 001 ab* 2 010 a*c 3 011 a** 4 100 *bc 5 101 *b* 6 110 **c 7 111 *** 

In Python, you can do it like this:

 def stars(input): l = len(input) for i in xrange(2**l): yield ''.join([('*' if i&(2**(l-pos-1)) else ch) for pos, ch in enumerate(input)]) 

Try:

 >>> print list(stars('abc')) ['abc', 'ab*', 'a*c', 'a**', '*bc', '*b*', '**c', '***'] 

Answer 3

The combinations method is used here:

 from itertools import combinations def stars(str): N,L = len(str), [] for k in range(0,N+1): for com in combinations(range(N),k): S = list(str) for x in com: S[x] = '*' L.append(''.join(S)) return L 

Try:

 >>> stars('abc') ['abc', '*bc', 'a*c', 'ab*', '**c', '*b*', 'a**', '***'] >>> stars('1234') ['1234', '*234', '1*34', '12*4', '123*', '**34', '*2*4', '*23*', '1**4', '1*3*', '12**', '***4', '**3*', '*2**', '1***', '****'] 

Answer 4

Or specific Python sees this function: http://docs.python.org/2/library/itertools.html#itertools.combinations