CODEWITHSUNDEEP
pythonrecursionbinary
Quiti
Quiti

Reputation: 132

Going through all binary combinations with some numbers as "?"

I have to generate all the possible binary representations of a given string, where some characters are "?" and others are 1 or 0.

I'm trying to do a recursive search but I encounter some weird problems I can't figure out.

userInput = list(input())
anslist = []
def fill(inp):
    #print(inp)
    if inp.count("?") == 0:
        print(inp, "WAS ADDED")
        anslist.append(inp)
        return


    for a in range(0, len(userInput)):
        if inp[a] == "?":
            inp[a] = 1
            fill(inp)
            inp[a] = 0
            fill(inp)
            return
print(anslist)

For the input ?01?1 I should be getting: 00101, 00111, 10101 and 10111 but I get 10111 10101 00101 printed out. In addition, anslist isn't working properly. I just can't seem to figure this out.

Upvotes: 3

Views: 221

Answers (5)

cdlane
cdlane

Reputation: 41905

A simple solution that avoids using a global or a library:

def fill(digits):

    if not digits:
        return []

    first, *rest = digits

    strings = fill(rest) if rest else ['']

    if first == '?':
        return ['0' + string for string in strings] + ['1' + string for string in strings]

    return [first + string for string in strings]

userInput = input()

print(fill(userInput))

Tries to spell things out rather than make the most efficient array operations, which is left as an exercise for the OP.

OUTPUT

> python3 test.py
?01?1
['00101', '00111', '10101', '10111']
> python3 test.py
???
['000', '001', '010', '011', '100', '101', '110', '111']
> python3 test.py
?
['0', '1']
> python3 test.py

[]
>

Upvotes: 2

Joran Beasley
Joran Beasley

Reputation: 114068

import itertools
import re

inp = "?01?1"
for combination in itertools.product("01", repeat=inp.count("?")):
    i_combination = iter(combination)
    print(re.sub("\?",lambda m: next(i_combination),inp))

this just uses the builtin itertools.product to create all possible strings of "01" of length N(however many question-marks there are in the string)

then it converts each one of those into an iterator where each item is consumed as soon as it is seen,

then we use re.sub to substitute our products into our original strings, in place of our question-marks

here it is in a repl https://repl.it/@JoranBeasley/AssuredAncientOpengroup

I see in a comment here you dont want to use builtins ... so nevermind then i guess

if you do not want to use builtin itertools.product .. .simply write your own

def my_product(s,r):
  if r < 1:
    yield ""
  for i in range(r):
    for c in s:
      for partial in  my_product(s,r-1):
        yield c+partial

same with built in iter

def my_iter(s):
    for c in s:
        yield c

and lastly we need to write our own custom subber

def my_substitute(s,replacement):
    iter_replacement = my_iter(replacement)
    while s.count("?"):
         s = s.replace("?",next(iter_replacement))
    return s

now we tie it all together in the same way

inp = "?01?1"
for combination in my_product("01", inp.count("?")):
    print(my_substitute(inp,combination))

Upvotes: 2

user24343
user24343

Reputation: 912

a list is a mutable type, that means that you only have one list on which all modifications are made. This causes your first call fill(inp) to also fill the remaining '?' in inp, thus only giving you one result with the second option for the first ? (first ?=1: two results, first ?=0: one result because the last result of the first ? is still saved in the list)

To resolve this problem, use list.copy(). This will pass a copy of the list to fill() and thus cause the original list to be left as it is.

Your complete code with .copy() and other minor modifications:

anslist = []
def fill(inp):
    if inp.count("?") == 0:
        print(inp, "WAS ADDED")
        anslist.append(inp)
        return

    for a in range(len(inp)):  # range(0, x) is equivalent to range(x); try to limit global variables
        if inp[a] == "?":
            inp[a] = 1
            fill(inp.copy())  # list is mutable
            inp[a] = 0
            fill(inp.copy())  # see above
            return
user_input = list(input())
fill(user_input)
print(anslist)

Upvotes: 2

Filip Młynarski
Filip Młynarski

Reputation: 3612

Here's example solution without using builtin tools. Here we use recursion, when we occur '?' during iterating over our input we replace it with '0' and '1' and add result of fill() of what's after current index.

userInput = input()

def fill(inp):
    ret = []
    for idx, i in enumerate(inp):
        if i == '?':
            for rest in fill(inp[idx+1:]):
                ret.append(inp[:idx] + '0' + rest)
                ret.append(inp[:idx] + '1' + rest)
            break
    else:
        return [inp]
    return ret

print(fill(userInput))

Output

?01?1 -> ['00101', '10101', '00111', '10111']
???   -> ['000', '100', '010', '110', '001', '101', '011', '111']

Upvotes: 2

Nikos M.
Nikos M.

Reputation: 8345

Sample python code using itertools.product (you can use an equivalent implementation but this is fine)

from itertools import product

def generate_combinations(inp):
   count = 0 
   for a in range(0, len(inp)):
      if inp[a] == "?": count += 1
   combinations = []
   for comb in product(range(2), repeat=count):
      pos = 0
      cinp = inp[:]
      for a in range(len(cinp)):
         if cinp[a] == '?':
           cinp[a] = str(comb[pos])
           pos += 1
       combinations.append(cinp)
    return combinations

example usage:

print(generate_combinations('?01?1'))

Upvotes: 1

Related Questions