有效地检查整数元组的二进制条件
Checking integer tuples for binary conditions efficiently
我正在编写一段代码,它采用 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 个整数列表也很棒!)
您只能 |=
到您的 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))
对我来说,这比固定的第二个解决方案快大约三倍。
我正在编写一段代码,它采用 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 个整数列表也很棒!)
您只能 |=
到您的 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))
对我来说,这比固定的第二个解决方案快大约三倍。