有效地检查整数元组的二进制条件

Question

我正在编写一段代码，它采用 5 个整数列表 (ships)、一个位掩码 (hits) 并输出 5 元组的数量（每个列表中的一个整数）符合以下两个条件：

一个。元组中没有两个整数在相同位置设置位。

乙。位掩码中的所有设置位也必须在元组中的整数之间设置。

我有以下有效的解决方案：

def noCollisionsBin(v, hits):
    tot = 0
    for i in v:
        if tot & i:
            return False
        tot |= i
    return (tot & hits) == hits

hits = 4224
ships = [[16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1],[25165824,17301504,12582912,540672,6291456,16896,3145728,528,786432,8650752,393216,270336,196608,8448,98304,264,24576,4325376,12288,135168,6144,4224,3072,132,768,2162688,384,67584,192,2112,96,66,24,1081344,12,33792,6,1056,3,33],[16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1],[25165824,17301504,12582912,540672,6291456,16896,3145728,528,786432,8650752,393216,270336,196608,8448,98304,264,24576,4325376,12288,135168,6144,4224,3072,132,768,2162688,384,67584,192,2112,96,66,24,1081344,12,33792,6,1056,3,33],[16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1]]

i=0
for ship1 in ships[0]:
    for ship2 in ships[1]:
        for ship3 in ships[2]:
            for ship4 in ships[3]:
                for ship5 in ships[4]:
                    if noCollisionsBin((ship1, ship2, ship3, ship4, ship5), hits):
                        i+=1

print(i) # Correctly outputs 1188564

但是，我不想生成所有可能的元组并检查每个元组的两个条件，而是想更有效地排除无效元组，例如，取两个整数并丢弃组合（如果它们在相同位置设置了位）位置（因此违反条件 A），然后再继续检查条件 B。

我尝试了以下方法，但它不起作用：

i=0

tot = 0
for ship1 in ships[0]:
    if (ship1 & tot):
        continue
    tot |= ship1
    for ship2 in ships[1]:
        if (ship2 & tot):
            continue
        tot |= ship2
        for ship3 in ships[2]:
            if (ship3 & tot):
                continue
            tot |= ship3
            for ship4 in ships[3]:
                if (ship4 & tot):
                    continue
                tot |= ship4
                for ship5 in ships[4]:
                    if (ship5 & tot):
                        continue
                    tot |= ship5
                    if (tot & hits) == hits:
                        i+=1

print(i) # incorrectly outputs 8

我做错了什么？

(PS。一种消除嵌套循环的递归方法，因此它适用于 n 个整数列表也很棒！）

Answer 1

您只能 |= 到您的 tot，您永远无法撤消它。您可以使用 tot1、tot2 等，例如：

tot1 = ship1
  ...
    tot2 = tot1 | ship2
      ...

一个可能更好的解决方案，灵感来自 Samwise 的建议，即在其文档中重用 itertools.product 的示例实现：

from collections import Counter

tots = Counter([0])
for shipp in ships:
    tots2 = Counter()
    for tot, freq in tots.items():
        for ship in shipp:
            if not tot & ship:
                tots2[tot | ship] += freq
    tots = tots2
print(sum(freq for tot, freq in tots.items() if tot & hits == hits))

对我来说，这比固定的第二个解决方案快大约三倍。

有效地检查整数元组的二进制条件

Checking integer tuples for binary conditions efficiently

python

combinations

combinatorics

bitmask