How do I iterate through all sub-combinations of 1's and !'s?

Question

Let's say I have a string that looks like "1000101"

I want to iterate over all possible ways to insert "!" where "1" is:

    1000101
    100010!
    1000!01
    1000!0!
    !000101
    !00010!
    !000!01
    !000!0!

scalable to any string and any number of "1"s

Answer 1

As (almost) always, itertools.product to the rescue:

>>> from itertools import product
>>> s = "10000101"
>>> all_poss = product(*(['1', '!'] if c == '1' else [c] for c in s))
>>> for x in all_poss:
...     print(''.join(x))
...     
10000101
1000010!
10000!01
10000!0!
!0000101
!000010!
!0000!01
!0000!0!

(Since we're working with one-character strings here we could even get away with

product(*('1!' if c == '1' else c for c in s))

if we wanted.)

Answer 2

Here you go. The recursive structure is that I can generate all the subcombos of s[1:] and then for each one of those combos I can insert in the front ! if s[0] is 1 and either way insert s[0]

def subcombs(s):
  if not s:
    return ['']

  char = s[0]
  res = []
  for combo in subcombs(s[1:]):
    if char == '1':
      res.append('!' + combo)
    res.append(char + combo)
  return res

print(subcombs('1000101'))
['!000!0!', '1000!0!', '!00010!', '100010!', '!000!01', '1000!01', '!000101', '1000101']

Answer 3

An approach with generator:

def possibilities(s):
    if not s:
        yield ""
    else:
        for s_next in possibilities(s[1:]):
            yield "".join([s[0], s_next])
            if s[0] == '1':
                yield "".join(['!', s_next])

print list(possibilities("1000101"))

Output:

['1000101', '!000101', '1000!01', '!000!01', '100010!', '!00010!', '1000!0!', '!000!0!']