此问题在一定程度上涉及算法(获得解决方案的最佳算法是什么)和Python问题(使用Python的哪些部分来有效地实现最佳算法)。
就算法而言:您可以定义位字符串到一组(相同大小的)位字符串的最大距离为目标位字符串与集合中任何一个字符串不同的位数。该算法的目标是查找具有与集合中字符串相同长度的新位字符串,其具有最低的最大距离。
假设所有起始位字符串都不同(因为它被定义为集合,而不是列表)。要计算的距离称为汉明距离,因此您正在寻找具有最小汉明距离的新位字符串以与一组起始字符串匹配。
生成正确长度的所有可能位字符串并计算到每个起始字符串的最大距离会暴力解决问题,可以使用回溯(一旦候选位字符串的最低当前最大值超过,则立即放弃结果)进行优化(*)。
(*: 对于想要纠正我的拼写的人,请考虑我使用的是英式英语,而不是美式英语-请随意提出改进意见)
但是,问题也可以被视为以下形式。
对于长度为1的位字符串,整个字符串空间只有两种选择,{'0','1'}
。这可以可视化为'0'
和'1'
位于长度为1的线段的两端,彼此距离为1。
对于长度为2的位字符串,整个字符串空间有4种选择,即0到3的位表示形式{'00','01','10','11'}
。 0距离1和2都是1,而1和2都距离3为1。当可视化时,它们形成正方形的四个角落,其中任何一个都不会比其他任何一个更远超过2步。
对于长度为3的位字符串,整个空间有8个选项,即0到7的位表示形式。可视化时,它们形成立方体的8个角,其中任何一个都不会比其他任何一个更远超过3步。
该模式继续(进入4D超立方体,5D等),找到答案的有效方法转化为:给定这些图表中的一组角落,请找到最低最大距离与任何一个角落。
给定这样的图表并查找这样一个点的算法将是:
- 首先将集合中的元素单独列出来; 如果只有一个元素,那就是微不足道的答案。
- 将当前距离设置为1。
- 针对所有集合,将仅与已在集合中的点相隔一步的任何点添加到其中。
- 交集所有产生的集合; 如果交集不为空,则这些点都是从起始点集开始的当前距离(或更少)的所有点; 否则,将当前距离增加1并转到步骤3。
对于长位字符串,通过跟踪添加到集合中的点来避免重复添加相同的点,可以进一步优化代码效率。即,不是将{'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
返回实际距离和所有最优答案,而不仅仅是一个。输出:
(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))
编辑:出于好奇,我将我的示例与问题中提供的原始示例进行了比较,发现它经常返回远非最优结果。我没有尝试找出原因,但我觉得有必要提一下。
有人指出,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]}