python - 从列表中两次尝试中查找一个元素出现的最大总和

Question

最好用例子来解释。如果 python 列表是 -

[[0,1,2,0,4],
 [0,1,2,0,2],
 [1,0,0,0,1],
 [1,0,0,1,0]]

我想选择两个子列表，它们将产生零出现次数的最大总和 - 其中总和的计算如下

SUM = No. of zeros present in the first selected sub-list + No. of zeros present in the second selected sub-list which were not present in the first selected sub-list.

在这种情况下，答案是 5。(第一个或第二个子列表和最后一个子列表)。 (请注意，不选择第三个子列表，因为它在第三个索引中有零，这与我们必须选择的第一/第二个子列表相同，并且总和为 4，如果我们考虑最后一个子列表)

如果我们要将其应用于大输入，哪种算法最适合？有没有比 N² 时间更好的方法来做到这一点？

Answer 1

二元运算对于这个任务非常有用:

1. 将每个子列表转换为二进制数，其中 0 变成 1 位，其他数字变成 0 位。

   例如，[0,1,2,0,4]会变成10010，也就是18。

2. 消除重复数字。

3. 将剩余的数字成对组合，并用二进制 OR 组合它们。
4. 找出最多 1 位的数字。

代码:

lists = [[0,1,2,0,4],
         [0,1,2,0,2],
         [1,0,0,0,1],
         [1,0,0,1,0]]

import itertools

def to_binary(lst):
    num = ''.join('1' if n == 0 else '0' for n in lst)
    return int(num, 2)

def count_ones(num):
    return bin(num).count('1')

# Step 1 & 2: Convert to binary and remove duplicates
binary_numbers = {to_binary(lst) for lst in lists}

# Step 3: Create pairs
combinations = itertools.combinations(binary_numbers, 2)

# Step 4 & 5: Compute binary OR and count 1 digits
zeros = (count_ones(a | b) for a, b in combinations)

print(max(zeros))  # output: 5