@din Ах, я упустил из виду тот факт, что результат не может содержать одинаковые векторы. Во всяком случае, я видел ваш вопрос довольно поздно, и я все еще перевариваю все детали проблемы. Я, вероятно, обновлю свой ответ в ближайшие дни. Вы заинтересованы в создании всех решений или только одного случайного решения за раз, и важно ли равномерное распределение?
отрим набор,Sвсех двоичных векторов длиныn где каждый содержит точноm из них; так что естьн-м нули в каждом векторе.
Моя цель - построить число,k, векторов изS так что эти векторы максимально отличаются друг от друга.
В качестве простого примера возьмемn= 4,m= 2 иk= 2, то возможное решение: [1,1,0,0] и [0,0,1,1].
Кажется, это открытая проблема в литературе по теории кодирования (?).
Есть ли способ (то есть алгоритм), чтобы найти неоптимальное, но хорошее решение?
Является ли расстояние Хэмминга правильным показателем эффективности для использования в этом случае?
Некоторые мысли:
ВЭта бумага, авторы предлагают пару алгоритмов для нахождения подмножества векторов, таких, что попарно расстояние Хэмминга> = определенное значение,d.
Случайный подход я реализовал следующим образом: взять наборSS, который инициализируется любым вектором изS, Затем я рассматриваю оставшиеся векторы вS, Для каждого из этих векторов я проверяю, имеет ли этот вектор хотя бы расстояниеd относительно каждого вектора вSS, Если так, то это добавлено кSS.
Взяв максимально возможноеd, если размерSS это> =kтогда я считаюSS в качестве оптимального решения, и я выбираю любое подмножествоk векторы изSS, Используя этот подход, я думаю, что в результатеSS будет зависеть от идентичности исходного вектора вSS; то есть есть несколько решений (?).
Но как поступить, если размерSS это <k ?
Из предложенных в статье алгоритмов я понял только случайный. Меня интересует бинарный лексикографический поиск (раздел 2.3), но я не знаю, как его реализовать (?).