Этот вопрос частично алгоритмический (какой алгоритм лучше всего подходит для решения) и частично вопрос Python (какие части Python использовать для эффективной реализации этого лучшего алгоритма).
По алгоритму: вы определяете максимальное расстояние для битовой строки до набора (одинакового размера) битовых строк как наибольшее число битов, на которое целевая битовая строка отличается от любой из строк в наборе. Цель алгоритма - найти новую битовую строку той же длины, что и строки в наборе, который имеет наименьшее максимальное расстояние.
Предполагается, что все начальные битовые строки различны (так как они определены как набор, а не список). Расстояние, которое вы вычисляете, называется расстоянием Хэмминга, поэтому вы ищете новую битовую строку с минимальным расстоянием Хемминга до начального набора строк.
Генерация всех возможных битовых строк правильной длины и вычисление максимального расстояния до каждой стартовой строки - грубая проблема, которая может быть оптимизирована (*) с помощью обратного отслеживания (отбрасывание результата, как только самый низкий максимальный ток будет превышен для битовая строка-кандидат).
(*: для людей, которые хотят исправить мое правописание, учтите, что я использую британский английский, а не американский английский - не стесняйтесь предлагать улучшения с учетом этого)
Однако проблему также можно рассматривать следующим образом.
Для битовых строк длиной 1 все пространство строк имеет только две опции, {'0', '1'}. Это можно представить как '0' и '1', сидящие на обоих концах отрезка линии длиной 1, оба на расстоянии 1 друг от друга.
Для битовых строк длиной 2 все пространство строк имеет 4 варианта, а именно битовые представления от 0 до 3 {'00', '01', '10', '11'} 0 - это расстояние 1 от 1 и 2, оба из которых находятся на расстоянии 1 от 3. Когда они визуализируются, они образуют четыре угла квадрата, ни один из которых не находится на расстоянии более двух шагов от любого другого.
Для битовых строк длиной 3 у всего пространства есть 8 опций, а именно битовые представления от 0 до 7. При визуализации образуют 8 углов куба, ни один из которых не превышает 3 шага от любого другого.
Этот паттерн продолжается (в 4-мерном гиперкубе, 5-мерном и т. Д.), И нахождение ответа на задачу эффективно приводит к следующему: при заданном наборе углов на одном из этих графиков найдите точку с наименьшим максимальным расстоянием до любого из им.
Алгоритм для нахождения такой точки, учитывая график, подобный этому:
- Начните со списка точек в наборе самих по себе; если есть только один, это тривиальный ответ.
- Установить текущее расстояние равным 1.
- Для всех наборов добавьте в него любую точку, находящуюся всего в одном шаге от точек, уже находящихся в наборе.
- Пересечь все получившиеся множества; если пересечение не пустое, это все точки, которые находятся на текущем (или меньшем) расстоянии от начального набора точек; в противном случае увеличьте текущее расстояние на 1 и перейдите к шагу 3.
Вероятно, это можно было бы оптимизировать и дальше, отслеживая посещенные точки по мере их добавления к наборам (для длинных битовых строк), чтобы избежать добавления одинаковых точек снова и снова, быстро замедляя данный алгоритм. То есть вместо того, чтобы превратить {'001'} в {'001', '101', '011', '000'}, вы можете перейти от [{'001'}] к [{'001'}, {'101', '011', '000'}] - объединение наборов по-прежнему дает вам все точки, достижимые за 1 или менее шагов, но следующий шаг в серии будет проще вычислить, найдя все точки, которые находятся на шаг дальше, но исключая точки в предыдущем направлении.
Нахождение точек на один шаг на самом деле довольно просто, если вы превращаете строки в числа, которые представляете, и вычисляете эксклюзивные побитовые числа или числа со всеми одиночными 1-битными числами с одинаковой битовой строкой. длина, т. е. чтобы найти все точки на расстоянии одного шага от '001', вы можете xor 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))
Редактировать: Из любопытства я проверил свой пример на оригинале, приведенном в вопросе, и обнаружил, что он часто возвращает далеко не оптимальный результат.Я не пытался выяснить, почему, но я решил, что стоит упомянуть.
Кто-то указал, что ОП может на самом деле хотеть точку с максимальным расстоянием Хэмминга до всех предоставленных битовых строк.С похожим подходом:
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]}