Given a pattern , we need to generate all possible binary numbers by filling the missing places in the pattern by 0 and 1.
E.g.
Pattern = "x1x";
Output :
010
110
011
111
Add a comment
|
6 Answers
This is relatively simple recursion and doesn't require the use of a library:
def process(patt):
if "x" not in patt:
print(patt)
else:
process(patt.replace("x", "0", 1))
process(patt.replace("x", "1", 1))
process("x1x")
OUTPUT
010
011
110
111
Comments
Here is another method using list(queue). It pops the first entry in the list and finds the first occurrence of "x" in the input string and replaces it by "0" and then "1" and then append these 2 new strings to the list. It goes until there is no "x" left in the list. I believe this one is one of the simplest way with a simple while loop:
def pattern_processor(list):
while "x" in list[0]:
item=list.pop(0)
list.append(item.replace("x", "0", 1))
list.append(item.replace("x", "1", 1))
return(list)
Driver code:
if __name__ == "__main__":
print(pattern_processor(["11x1x"]))
output:
['11010', '11011', '11110', '11111']
Comments
Try this way :
def pattern(str1, idx):
str = list(str1)
if idx == len(str):
print(''.join(str))
return 0
if str[idx] == 'x':
# replace 'x' by '0' and recurse
str[idx] = '0'
pattern(str, idx + 1)
# replace 'x' by '1' and recurse
str[idx] = '1'
pattern(str, idx + 1)
# No need to backtrack as string is passed by value to the function
else:
pattern(str, idx + 1)
str = "x1x"
pattern(str, 0)
Output :
010
011
110
111
Comments
This is one possible way to solve it using itertools:
import itertools
pattern = "x1x"
a = [['0','1'] if (c == 'x') else c for c in pattern]
b = [''.join(lst) for lst in list(itertools.product(*a))]
for s in b:
print(s)
Output:
010
110
011
111
Comments
Here's yet another one making use of the python regular expression module re and itertool as seen in other answers already.
import re
import itertools
pattern = 'x1x'
patt = re.compile(pattern.replace('x', '.'))
pattern_length = len(pattern)
perms = [ '1','0'] *pattern_length
ls = list()
for x in itertools.permutations(perms, pattern_length):
ls.append(x)
func = lambda x: ''.join(x)
keep = list()
for x in ls:
x_ = func(x)
if patt.match(x_) and not x_ in keep:
keep.append(x_)
for k in keep:
print k
ouput:
110
111
011
010
Comments
I think you could use itertools.product([0, 1], repeat=2), and then filter the output to suit your needs:
>>> import itertools
>>>
>>> [''.join(x) for x in itertools.product(['0', '1'], repeat=3) if x[1] == '1']
['010', '011', '110', '111']
1 Comment
Nir Alfasi
And if the input is "xx1" ? ;)