bitwise OR reduction of python lists

Question

I have two lists of zeros and ones. Both lists are of same length. The following is just an example, i am looking for a generic solution for lists of any sizes and with zeros and ones at any index.

l1 = [1,1,0,1,1,1,1]
l2 = [0,0,0,1,0,0,0]

The goal is to use the first list l1 as mask to create a new list l2_new from l2 that logicaly OR merges all elements of indizes where l1 is 1 and adopts elements unchanged where l1 is 0.

Which would result to:

l2_new = [0,0,1]

Graphical explanation:

Divakar · Accepted Answer · 2020-06-29T10:31:09.787

2

That's a perfect setup for np.bitwise_or.reduceat that does slice-based OR-ing -

# Based on https://stackoverflow.com/a/62430810/ @Divakar
def squash1s_mask(a):
    a = np.asarray(a)
    m = a==1
    return np.r_[True,m[:-1]!=m[1:]] | (a==0)

out = np.bitwise_or.reduceat(l2, np.flatnonzero(squash1s_mask(l1)))

edited Jun 29 '20 at 10:31

answered Jun 18 '20 at 13:38

Divakar

218,885
19
262
358

GODLIKE!! So now coming to the last question of this series, maybe you have another numpy magic hand on this one: https://stackoverflow.com/questions/62407188/combine-python-list-elements-where-value-is-1-plus-an-offset-masking (its the combination of the last question, this one and an additional preceiding task) – gustavz Jun 18 '20 at 13:50
unfortunately this answer is not correct, for `l2=[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]` `l1=[1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0]` it leads to `[1, 0, 0, 0]`, whereas the correct result would be `[1, 0, 0, 0, 0, 0, 0]` – gustavz Jun 29 '20 at 10:01
@gustavz My understanding was that there are islands of 0s and 1s in `l1` and we need to reduce chunks off `l2` based on those islands. So, the number of elements in the output would be same as number of those islands. With your latest setup for `l1`, it has 4 such islands and hence 4 output elements. Did I misunderstand it? – Divakar Jun 29 '20 at 10:12
no the idea is to use `l1` as a mask for `l2`: Where `l1` is `1` the elements in `l2` should be reduced with a logical `OR` - **BUT** where `l1` is `0` all elements of `l2` should remain untouched. – gustavz Jun 29 '20 at 10:18
1

@gustavz Okay, the idea is that squashing based on your other questioin it seems. Check out edited post. – Divakar Jun 29 '20 at 10:31

score 1 · Answer 2 · answered Jun 18 '20 at 10:04

This should work. Approach is simple.

Wherever you find 1, check for consecutive 1's and mark the start, end index. OR the entries for this range from l2.

Wherever you find 0, copy the respective element from l2

index = 0

prev = 0
res = []
while index < len(l1):
    if l1[index] == 1:
        prev = index
        while index < len(l1) and l1[index] == 1:
            index += 1

        tmp = 0
        for i in range(prev,index):
            tmp = tmp|l2[i]
        res.append(tmp)

    elif l1[index] == 0:
        res.append(l2[index])
        index += 1

print(res)

score 1 · Answer 3 · answered Jun 18 '20 at 10:07

One way is to use itertools.groupby:

import itertools 
l1 = [1,1,0,1,1,1,1]
l2 = [0,0,0,1,0,0,0]
pos = [(item, pos) for pos, item in enumerate(l1)]
#[(1, 0), (1, 1), (0, 2), (1, 3), (1, 4), (1, 5), (1, 6)]

result = []
for key, group in itertools.groupby(pos, lambda x: x[0]):
    if key == 0:
        #if group is all 0 then we don't change anything
        result.extend(l2[g[1]] for g in group)
    else:
        #else do OR operation in current group and append to final list
        current = 0
        for g in group:
            current |= l2[g[1]]
        result.append(current)
result
#[0, 0, 1]

score 1 · Answer 4 · answered Jun 18 '20 at 10:24

This might help; a simple loop without a lot of additional variables.

l1 = [1, 1, 0, 1, 1, 1, 1]
l2 = [0, 0, 0, 1, 0, 0, 0]

answer = []
or_result = 0
index = 0

while index < len(l1):
    # while 1, OR the elements of l2
    while index < len(l1) and l1[index] == 1:
        or_result ^= l2[index]
        index += 1

    answer.append(or_result)

    # while 0, append the elements of l2 as they are
    while index < len(l1) and l1[index] == 0:
        answer.append(l2[index])
        index += 1

    or_result = 0

print(answer)

score 1 · Answer 5 · answered Jun 18 '20 at 10:42

Similar to the answer by @ExplodingGayFish, but I apply groupby on both lists at the same time, and use functional approach to calculate OR.

from functools import reduce
from itertools import groupby
from operator import or_


def fn(l1, l2):
    result = []

    # group both lists by the values in l1
    for key, group in groupby(zip(l1, l2), key=lambda x: x[0]):
        # extract values from l2
        group_from_l2 = [x[1] for x in group]
        if key == 1:
            # bitwise OR of all values in group_from_l2
            result.append(reduce(or_, group_from_l2))
        else:
            # group_from_l2 unchanged
            result.extend(group_from_l2)

    return result

>>> fn([1, 1, 0, 1, 1, 1, 1], [0, 0, 0, 1, 0, 0, 0])
[0, 0, 1]
>>> fn([1, 1, 0, 0, 1, 1, 0, 0], [0, 1, 1, 0, 1, 1, 0, 1])
[1, 1, 0, 1, 0, 1]

bitwise OR reduction of python lists

5 Answers5

Linked