4

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.

Jeremy K
  • 523
  • 1
  • 6
  • 20
  • Theory and psuedo code here: http://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string – ficuscr Nov 07 '12 at 17:32
  • This isn't about permutations -- if anything, he need to iterate over all subsequences of characters – Ian Clelland Nov 07 '12 at 17:37
  • I guess your second example should return `['x2', '1x', 'xx']` and your third should return `['x23', '1x3', '12x', 'xx3', 'x2x', '1xx', 'xxx']` – Vortexfive Nov 07 '12 at 17:44

4 Answers4

8

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. :^)

DSM
  • 342,061
  • 65
  • 592
  • 494
  • This was exactly the kind of answer I had hoped for. Thank you very much. I'll pick apart the list comprehension so I get a better understanding of what it's doing. I also really liked your binary switch idea. Thanks again. – Jeremy K Nov 07 '12 at 17:47
  • Glad to help. `product`, `zip`, and `cycle` are handy (`zip` most of all, everyone uses that.) If this is for a class, it's probably a good idea to work through either the binary or the recursive approach, though. – DSM Nov 07 '12 at 17:49
  • +1. I implemented the binary approach and then saw your answer. – Steven Rumbalski Nov 07 '12 at 17:57
  • Not for class, just for fun. It's for Project Euler problem 51 which I just solved with your help. Might be a crazy way to solve it but it works. – Jeremy K Nov 07 '12 at 18:51
  • +1 - nothing constructive to add, just one of those awesome answers that makes me want to get better at Python :) – RocketDonkey Nov 08 '12 at 02:06
2

You can look at this as a problem of finding and iterating over all subsequences of characters in your original string. (For every subsequence, replace the characters in it by '*', 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 iterate over them is to iterate over the integers from 0 to (2^N)-1, and use their binary representations as the indications of whether the character should be replaced or not

For 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 could 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 it out:

>>> print list(stars('abc'))
['abc', 'ab*', 'a*c', 'a**', '*bc', '*b*', '**c', '***']
Ian Clelland
  • 43,011
  • 8
  • 86
  • 87
1

Here's a way using combinations :

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 it out:

>>> 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***', '****']
Sam
  • 366
  • 1
  • 5
0

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

ficuscr
  • 6,975
  • 2
  • 32
  • 52