搜索最不像一组位串的位串
Search for bitstring most unlike a set of bitstrings
我有一组位串：{'0011', '1100', '1110'}（一组中的所有位串长度相同）。
我想快速找到与集合最大相似度最小的相同长度的位串。最大相似度可以这样计算：
def max_similarity(bitstring, set):
max = 0
for item in set:
temp = 0
for i in range(len(bitstring)):
if bitstring[i] == item[i]:
temp += 1
if temp > max:
max = temp
return max
我知道我可以遍历该长度的所有可能位串，计算每个位串的最大相似度，最后保留这些迭代中最小的一个。但这解决了 O(2^n) 中的问题。我想知道是否有人看到任何更快的替代方案。
我一直在玩弄 Python 异或：
def int2bin(integer, digits):
if integer >= 0:
return bin(integer)[2:].zfill(digits)
else:
return bin(2**digits + integer)[2:]
def XOR(bitset):
intset = [int('{}'.format(bitstring), 2) for bitstring in bitset]
digits = len(bitset.pop())
if len(intset) == 1:
return int2bin(~intset.pop(), digits)
else:
curr = 0
while intset:
curr = curr ^ intset.pop()
return int2bin(curr, digits)
if __name__ == '__main__':
bitset1 = {'0011', '1100', '1110'}
bitset2 = {'01001', '11100', '10111'}
print(XOR(bitset1))
print(XOR(bitset2))
>>> python test.py
0001
00010
（从 here 窃取的函数 int2bin）
但我发现它适用于某些输入，但不适用于其他输入。在上面的测试中，它为 bitset2 找到了正确的解决方案，但没有为 bitset1 找到正确的解决方案。 O(2^n) 以下的任何解决方案可用吗？
这个问题部分是算法问题（获得解决方案的最佳算法是什么），部分是 Python 问题（关于 Python 的哪些部分可以用来有效地实现最佳算法）。
关于算法：您将位串到一组（相同大小）位串的最大距离定义为目标位串与该组中的任何串不同的最大位数。该算法的目标是找到一个新的位串，其长度与集合中具有最小最大距离的串的长度相同。
假设所有的起始位串都是不同的（因为它被定义为一个集合，而不是一个列表）。您正在计算的距离称为汉明距离，因此您正在寻找与起始字符串集具有最小汉明距离的新位串。
生成所有可能的正确长度的位串并计算到每个起始串的最大距离是暴力强制问题，可以使用回溯优化（*）（一旦最低当前最大值为丢弃结果超过候选位串）。
(*：对于希望纠正我的拼写的人，请考虑我使用的是英国英语，而不是美国英语这一事实 - 考虑到这一点，请随时提出改进建议)
不过问题也可以这样看。
对于长度为1的位串，整个space串只有两个选项，{'0', '1'}。这可以想象为 '0' 和 '1' 位于长度为 1 的线段的两端，彼此之间的距离为 1。
对于长度为2的位串，整个space串有4个选项，即0到3的位表示{'00', '01', '10', '11'} 0是1到1和2的距离，都是它们与 3 的距离为 1。当可视化时，它们形成正方形的四个角，none 其中与其他角的距离超过 2 步。
对于长度为3的位串，整个space有8个选项，即0到7的位表示。可视化时，形成立方体的8个角，none他们与其他任何人的距离都超过 3 步。
此模式继续（进入 4D 超立方体、5D 等）并有效地找到问题的答案 t运行变成：给定其中一个图上的一组角点，找到点与其中任何一个的最大距离最小。
找到这样一个点的算法，给定这样的图将是：
- 从一个集合中的点列表开始；如果只有一个，那就是微不足道的答案。
- 将当前距离设置为 1。
- 对于所有集合，将任何点添加到集合中已有的点仅一步之遥。
- 与所有结果集相交；如果交点不为空，则这些是距起始点集当前距离（或更小）的所有点；否则，将当前距离增加 1 并转到步骤 3。
这可能会通过在将访问的点添加到集合（对于长位串）时跟踪访问的点来进一步优化，以避免一遍又一遍地添加相同的点，从而迅速减慢给定的算法。 IE。你可以从 [{'001'}] 到 [{'001'}, {'101', '011', '000'}] 而不是将 {'001'} 变成 {'001', '101', '011', '000'} - 集合的并集仍然可以让你在 1 个或更少的步骤内到达所有点，但是该系列的下一步会更容易计算，方法是找到距离更远一步的所有点，但不包括前一个方向的点。
找点一步其实很简单，如果你把字符串变成代表的数字，并计算排他性的位或与所有单个'1'位数字相同的数字位串长度，即要找到距 '001' 一步之遥的所有点，您可以将 1 与 4、2 和 1 异或，得到 {5, 3, 0}, 匹配正确的点。
将所有这些放在 Python 的紧凑位中（没有对较长字符串进行优化）：
def closest(strings):
if len(strings) == 1:
return next(iter(strings))
size = len(next(iter(strings)))
points = [{int(s, 2)} for s in strings]
powers = {1 << n for n in range(size)}
d = 0
while True:
d += 1
points = [{n ^ p for p in powers for n in nums} | nums for nums in points]
intersection = set.intersection(*points)
if len(intersection) > 0:
return d, {f"{n:b}".zfill(size) for n in intersection}
print(closest({'1000', '0001', '0011'}))
请注意 closest returns 实际距离和所有最佳答案，而不仅仅是一个。输出：
(2, {'0000', '0010', '1001', '0001', '1011'})
将讨论的优化添加到 closest:
def closest_optimised(strings):
if len(strings) == 1:
return next(iter(strings))
size = len(next(iter(strings)))
points = [({int(s, 2)}, {int(s, 2)}) for s in strings]
powers = {1 << n for n in range(size)}
d = 0
while True:
d += 1
new_points = [{n ^ p for p in powers for n in rp} - ap for ap, rp in points]
points = [(ap | np, np) for (ap, _), np in zip(points, new_points)]
intersection = set.intersection(*[ap for ap, _ in points])
if len(intersection) > 0:
return d, {f"{n:b}".zfill(size) for n in intersection}
请注意，运行 通过分析器优化代码 运行 这些设置的平均时间约为一半：
from random import randint
s = 10
x = 500
numbers = [randint(0, 2**s-1) for _ in range(x)]
number_strings = {f"{n:b}".zfill(s) for n in numbers}
print(number_strings)
print(closest_optimised(number_strings))
print(closest(number_strings))
编辑：出于好奇，我 运行 我的示例与问题中给出的原始示例相对照，发现它经常 returns 远非最佳结果。我没有试图找出原因，但我认为值得一提。
有人指出，OP实际上可能想要与所有提供的位串具有最大汉明距离的点。使用类似的方法：
def farthest(strings):
s = next(iter(strings))
size = len(s)
if len(strings) == 1:
return ''.join(['0' if c == '1' else '1' for c in s])
all_visited = {int(s, 2) for s in strings}
visited = [set(), all_visited]
powers = {1 << n for n in range(size)}
d = 0
while True:
d += 1
visited.append({n ^ p for p in powers for n in visited[-1]} - all_visited)
all_visited = all_visited | visited[-1]
if len(all_visited) == 2**size:
return d, {f"{n:b}".zfill(size) for n in visited[-1]}
这是一个成本为 O(n * b) 的算法，其中 n 是集合的大小，b 是固定的位长度。
该算法的直觉是检查每个位索引（0 或 1）的多数位位置并相应地评分。
更高的分数意味着给定的位串有位位置
这与大多数人背道而驰。虽然，我没有处理过领带。
import operator
def max_hamming(bitstrings):
n_bits = len(bitstrings[0])
# Track bit set/unset for each bit position
scores = {
n: {'0': [], '1': []} for n in range(n_bits)
}
# Increment on each bit position if not with the majority
total = {b: 0 for b in bitstrings}
# O(b * n)
for n in range(n_bits):
n_set = 0
for b in bitstrings:
is_set = b[n]
scores[n][is_set].append(b)
if is_set:
n_set += 1
# If majority have this bit set, give a point to those with unset or vice versa
outliers = scores[n]['0'] if n_set > len(bitstrings) else scores[n]['1']
for s in outliers:
total[s] += 1
return max(total.items(), key=operator.itemgetter(1))[0]
另请注意，我传递的是列表而不是集合，因为 python 集合的顺序不确定。
用法：
bitset1 = [
'0011',
'1100',
'1110'
]
bitset2 = [
'01001',
'11100',
'10111'
]
print(max_hamming(bitset1))
print(max_hamming(bitset2))
我可以使用 numpy 还是这应该是一种算法？让我们假设一切都是 bitstring 就像你拥有的那样。
import numpy as np
def bitstring2np(bitstring):
"""
Convert a bitstring to np.array
i.e. '0011' to np.array([0, 0, 1, 1])
"""
return np.array([int(bit) for bit in bitstring], dtype=int)
def unlike(bitset):
"""
Gets the most 'unlike' string between a bitset.
Accomplishes this by creating a 2D array from the bitsets,
figuring out the number of 1s in a column, and if that
number of 1s is >=50%, then gives it a 0 in that place, otherwise
gives it a 1.
"""
bset = list(bitset)
# Create an empty 2D array to store the bitsets into
arr = np.empty((len(bset), len(bset[0])), dtype=int)
for idx in range(len(bset)):
# Store that bitset into the row of our array
arr[idx,:] = bitstring2np(bset[idx])
# Count the number of 1's in each column
nonzero = np.count_nonzero(arr, axis=0)
total = len(bset) # how many to compare against
# Since you want the most unlike and since we are counting
# number of 1s in a column, if the rate is >=.5 give it a 0, otherwise
# 1
most_unlike = ''.join('0' if count/total >=.5 else '1' for count in nonzero)
return most_unlike
>>> print(unlike(bitset1))
0001
>>> print(unlike(bitset2))
00010
现在我知道你说 0001 不是 bitset 的正确解决方案，但我很确定它是正确的，除非我没有正确理解问题。
我有一组位串：{'0011', '1100', '1110'}（一组中的所有位串长度相同）。
我想快速找到与集合最大相似度最小的相同长度的位串。最大相似度可以这样计算：
def max_similarity(bitstring, set):
max = 0
for item in set:
temp = 0
for i in range(len(bitstring)):
if bitstring[i] == item[i]:
temp += 1
if temp > max:
max = temp
return max
我知道我可以遍历该长度的所有可能位串，计算每个位串的最大相似度，最后保留这些迭代中最小的一个。但这解决了 O(2^n) 中的问题。我想知道是否有人看到任何更快的替代方案。
我一直在玩弄 Python 异或：
def int2bin(integer, digits):
if integer >= 0:
return bin(integer)[2:].zfill(digits)
else:
return bin(2**digits + integer)[2:]
def XOR(bitset):
intset = [int('{}'.format(bitstring), 2) for bitstring in bitset]
digits = len(bitset.pop())
if len(intset) == 1:
return int2bin(~intset.pop(), digits)
else:
curr = 0
while intset:
curr = curr ^ intset.pop()
return int2bin(curr, digits)
if __name__ == '__main__':
bitset1 = {'0011', '1100', '1110'}
bitset2 = {'01001', '11100', '10111'}
print(XOR(bitset1))
print(XOR(bitset2))
>>> python test.py
0001
00010
（从 here 窃取的函数 int2bin）
但我发现它适用于某些输入，但不适用于其他输入。在上面的测试中，它为 bitset2 找到了正确的解决方案，但没有为 bitset1 找到正确的解决方案。 O(2^n) 以下的任何解决方案可用吗？
这个问题部分是算法问题（获得解决方案的最佳算法是什么），部分是 Python 问题（关于 Python 的哪些部分可以用来有效地实现最佳算法）。
关于算法：您将位串到一组（相同大小）位串的最大距离定义为目标位串与该组中的任何串不同的最大位数。该算法的目标是找到一个新的位串，其长度与集合中具有最小最大距离的串的长度相同。
假设所有的起始位串都是不同的（因为它被定义为一个集合，而不是一个列表）。您正在计算的距离称为汉明距离，因此您正在寻找与起始字符串集具有最小汉明距离的新位串。
生成所有可能的正确长度的位串并计算到每个起始串的最大距离是暴力强制问题，可以使用回溯优化（*）（一旦最低当前最大值为丢弃结果超过候选位串）。
(*：对于希望纠正我的拼写的人，请考虑我使用的是英国英语，而不是美国英语这一事实 - 考虑到这一点，请随时提出改进建议)
不过问题也可以这样看。
对于长度为1的位串，整个space串只有两个选项，{'0', '1'}。这可以想象为 '0' 和 '1' 位于长度为 1 的线段的两端，彼此之间的距离为 1。
对于长度为2的位串，整个space串有4个选项，即0到3的位表示{'00', '01', '10', '11'} 0是1到1和2的距离，都是它们与 3 的距离为 1。当可视化时，它们形成正方形的四个角，none 其中与其他角的距离超过 2 步。
对于长度为3的位串，整个space有8个选项，即0到7的位表示。可视化时，形成立方体的8个角，none他们与其他任何人的距离都超过 3 步。
此模式继续（进入 4D 超立方体、5D 等）并有效地找到问题的答案 t运行变成：给定其中一个图上的一组角点，找到点与其中任何一个的最大距离最小。
找到这样一个点的算法，给定这样的图将是：
- 从一个集合中的点列表开始；如果只有一个，那就是微不足道的答案。
- 将当前距离设置为 1。
- 对于所有集合，将任何点添加到集合中已有的点仅一步之遥。
- 与所有结果集相交；如果交点不为空，则这些是距起始点集当前距离（或更小）的所有点；否则，将当前距离增加 1 并转到步骤 3。
这可能会通过在将访问的点添加到集合（对于长位串）时跟踪访问的点来进一步优化，以避免一遍又一遍地添加相同的点，从而迅速减慢给定的算法。 IE。你可以从 [{'001'}] 到 [{'001'}, {'101', '011', '000'}] 而不是将 {'001'} 变成 {'001', '101', '011', '000'} - 集合的并集仍然可以让你在 1 个或更少的步骤内到达所有点，但是该系列的下一步会更容易计算，方法是找到距离更远一步的所有点，但不包括前一个方向的点。
找点一步其实很简单，如果你把字符串变成代表的数字，并计算排他性的位或与所有单个'1'位数字相同的数字位串长度，即要找到距 '001' 一步之遥的所有点，您可以将 1 与 4、2 和 1 异或，得到 {5, 3, 0}, 匹配正确的点。
将所有这些放在 Python 的紧凑位中（没有对较长字符串进行优化）：
def closest(strings):
if len(strings) == 1:
return next(iter(strings))
size = len(next(iter(strings)))
points = [{int(s, 2)} for s in strings]
powers = {1 << n for n in range(size)}
d = 0
while True:
d += 1
points = [{n ^ p for p in powers for n in nums} | nums for nums in points]
intersection = set.intersection(*points)
if len(intersection) > 0:
return d, {f"{n:b}".zfill(size) for n in intersection}
print(closest({'1000', '0001', '0011'}))
请注意 closest returns 实际距离和所有最佳答案，而不仅仅是一个。输出：
(2, {'0000', '0010', '1001', '0001', '1011'})
将讨论的优化添加到 closest:
def closest_optimised(strings):
if len(strings) == 1:
return next(iter(strings))
size = len(next(iter(strings)))
points = [({int(s, 2)}, {int(s, 2)}) for s in strings]
powers = {1 << n for n in range(size)}
d = 0
while True:
d += 1
new_points = [{n ^ p for p in powers for n in rp} - ap for ap, rp in points]
points = [(ap | np, np) for (ap, _), np in zip(points, new_points)]
intersection = set.intersection(*[ap for ap, _ in points])
if len(intersection) > 0:
return d, {f"{n:b}".zfill(size) for n in intersection}
请注意，运行 通过分析器优化代码 运行 这些设置的平均时间约为一半：
from random import randint
s = 10
x = 500
numbers = [randint(0, 2**s-1) for _ in range(x)]
number_strings = {f"{n:b}".zfill(s) for n in numbers}
print(number_strings)
print(closest_optimised(number_strings))
print(closest(number_strings))
编辑：出于好奇，我 运行 我的示例与问题中给出的原始示例相对照，发现它经常 returns 远非最佳结果。我没有试图找出原因，但我认为值得一提。
有人指出，OP实际上可能想要与所有提供的位串具有最大汉明距离的点。使用类似的方法：
def farthest(strings):
s = next(iter(strings))
size = len(s)
if len(strings) == 1:
return ''.join(['0' if c == '1' else '1' for c in s])
all_visited = {int(s, 2) for s in strings}
visited = [set(), all_visited]
powers = {1 << n for n in range(size)}
d = 0
while True:
d += 1
visited.append({n ^ p for p in powers for n in visited[-1]} - all_visited)
all_visited = all_visited | visited[-1]
if len(all_visited) == 2**size:
return d, {f"{n:b}".zfill(size) for n in visited[-1]}
这是一个成本为 O(n * b) 的算法，其中 n 是集合的大小，b 是固定的位长度。
该算法的直觉是检查每个位索引（0 或 1）的多数位位置并相应地评分。
更高的分数意味着给定的位串有位位置 这与大多数人背道而驰。虽然，我没有处理过领带。
import operator
def max_hamming(bitstrings):
n_bits = len(bitstrings[0])
# Track bit set/unset for each bit position
scores = {
n: {'0': [], '1': []} for n in range(n_bits)
}
# Increment on each bit position if not with the majority
total = {b: 0 for b in bitstrings}
# O(b * n)
for n in range(n_bits):
n_set = 0
for b in bitstrings:
is_set = b[n]
scores[n][is_set].append(b)
if is_set:
n_set += 1
# If majority have this bit set, give a point to those with unset or vice versa
outliers = scores[n]['0'] if n_set > len(bitstrings) else scores[n]['1']
for s in outliers:
total[s] += 1
return max(total.items(), key=operator.itemgetter(1))[0]
另请注意，我传递的是列表而不是集合，因为 python 集合的顺序不确定。
用法：
bitset1 = [
'0011',
'1100',
'1110'
]
bitset2 = [
'01001',
'11100',
'10111'
]
print(max_hamming(bitset1))
print(max_hamming(bitset2))
我可以使用 numpy 还是这应该是一种算法？让我们假设一切都是 bitstring 就像你拥有的那样。
import numpy as np
def bitstring2np(bitstring):
"""
Convert a bitstring to np.array
i.e. '0011' to np.array([0, 0, 1, 1])
"""
return np.array([int(bit) for bit in bitstring], dtype=int)
def unlike(bitset):
"""
Gets the most 'unlike' string between a bitset.
Accomplishes this by creating a 2D array from the bitsets,
figuring out the number of 1s in a column, and if that
number of 1s is >=50%, then gives it a 0 in that place, otherwise
gives it a 1.
"""
bset = list(bitset)
# Create an empty 2D array to store the bitsets into
arr = np.empty((len(bset), len(bset[0])), dtype=int)
for idx in range(len(bset)):
# Store that bitset into the row of our array
arr[idx,:] = bitstring2np(bset[idx])
# Count the number of 1's in each column
nonzero = np.count_nonzero(arr, axis=0)
total = len(bset) # how many to compare against
# Since you want the most unlike and since we are counting
# number of 1s in a column, if the rate is >=.5 give it a 0, otherwise
# 1
most_unlike = ''.join('0' if count/total >=.5 else '1' for count in nonzero)
return most_unlike
>>> print(unlike(bitset1))
0001
>>> print(unlike(bitset2))
00010
现在我知道你说 0001 不是 bitset 的正确解决方案，但我很确定它是正确的，除非我没有正确理解问题。