Varun Suryan - 6 months ago 28

Python Question

I have two equal sized arrays ( array1 and array2 ) of 0's and 1's. How do I get all the arrays whose bit wise union with array1 result into array2 ? For example,if array1 = [1, 1, 1] and array2 = [1, 1, 1]. Output should be all eight arrays : [0, 0, 0], [1, 0, 0], ...., [1, 1, 1] . Are there efficient solutions to it or only brute force is the way ?

My try :

I tried to calculate bit wise difference first and if any of bit is negative then return false( not possible to combine first array with any kind of array to get array2). If all bits are non-negative then .... if bit in difference is 0 then it can be replaced by 0 or 1 either( this is wrong assumption albeit and fails for if array1= [0,0] , array2= [0,0], and if any bit in difference is 0 then required array has to have 1 at that place to make it 1

Answer

You can construct the digit options for each slot `i`

by evaluating:

```
for d in (0, 1):
if (array1[i] or d) == array2[i]):
digits[i].append(d)
```

Then you just need to iterate over `i`

.

The objective is to construct a list of lists: `[[0,1],[1],[0,1]]`

showing the valid digits in each slot. Then you can use `itertools.product()`

to construct all of the valid arrays:

```
arrays = list(itertools.product(*digits))
```

You can put all this together using list comprehensions and this would result in:

```
list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(array1, array2)]))
```

In action:

```
>>> import itertools as it
>>> a1, a2 = [1,1,1], [1,1,1]
>>> list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(a1, a2)]))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
>>> a1, a2 = [1,0,0], [1,1,1]
>>> list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(a1, a2)]))
[(0, 1, 1), (1, 1, 1)]
>>> a1, a2 = [1,0,0], [0,1,1]
>>> list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(a1, a2)]))
[]
```