Нахождение числа максимально различных бинарных векторов из набора

Question

Рассмотрим множество 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 равен <<em> k ?
Из предложенных в статье алгоритмов я имеюпонял только Случайный.Меня интересует бинарный лексикографический поиск (раздел 2.3), но я не знаю, как его реализовать (?).

Answer 1

Я не знаю, является ли максимальное суммирование расстояний Хэмминга лучшим критерием для получения набора «максимально различных» двоичных векторов, но я сильно подозреваю, что это так.Кроме того, я сильно подозреваю, что алгоритм, который я собираюсь представить, дает в точности набор из k векторов, который максимизирует сумму расстояний Хэмминга для векторов из n битов с m единицами и n - m нулями.К сожалению, у меня нет времени, чтобы доказать это (и, конечно, я могу ошибаться - в этом случае у вас останется «неоптимальное, но хорошее» решение, согласно вашему запросу).

Предупреждение: в дальнейшем я предполагаю, что в качестве дополнительного условия набор результатов может не содержать один и тот же вектор дважды.

Я предлагаю следующий алгоритм:

Начиная с набора результатов только с одним вектором, несколько раз добавьте один из тех оставшихся векторов, которые имеют максимальную сумму расстояний Хэмминга от всех векторов, которые уже находятся в наборе результатов.Остановитесь, когда результирующий набор содержит k векторов или все доступные векторы были добавлены.

Обратите внимание, что сумма расстояний Хэмминга результирующего набора не зависит от выбора первого или любого последующего вектора.

Я нашел подход «грубой силы» жизнеспособным, учитывая ограничения, которые вы упомянули в комментарии:

n <25, 1

Answer 2

ОБНОВЛЕННЫЙ ОТВЕТ

Глядя на пример вывода кода Уолтера Тросса, я думаю, что генерация случайного решения может быть упрощена до следующего:

Возьмем любой вектор для начала, например, для n= 8, m = 3, k = 5:

A:   01001100  

После каждого шага суммируйте векторы, чтобы узнать, сколько раз использовалась каждая позиция:

SUM: 01001100

Затем,для следующего вектора поместите те в позиции, которые использовались меньше всего (в данном случае ноль раз), например:

B:   00110001

, чтобы получить:

A:   01001100  
B:   00110001
SUM: 01111101  

Тогда естьОсталось 2 наименее используемых позиции, поэтому для 3 позиций в следующем векторе используйте эти 2 позиции, а затем поместите третью в любом месте:

C:   10010010

, чтобы получить:

A:   01001100  
B:   00110001
C:   10010010
SUM: 11121111  (or reset to 00010000 at this point)  

Затем для следующего вектора у вас есть 7 наименее используемых позиций (те, которые в сумме), поэтому выберите любые 3, например:

D:   10100010

, чтобы получить:

A:   01001100  
B:   00110001
C:   10010010
D:   10100010
SUM: 21221121  

И в качестве конечного вектора выберите любую из 4 наименее используемых позиций, например:

E:   01000101

---

Чтобы сгенерировать все решения, просто сгенерируйте всеy возможный вектор на каждом шаге:

A:   11100000, 11010000, 11001000, ... 00000111

Затем, например, когда A и SUM равны 11100000:

B:   00011100, 00011010, 00011001, ... 00000111

Затем, например, когда B равно 00011100 и SUM равно 11111100:

C:   10000011, 01000011, 00100011, 00010011, 00001011, 00000111

Затем, например, когда C равно 10000011, а SUM равно 21111111:

D:   01110000, 01101000, 01100100, ... 00000111

И, наконец, например, когда D равно 01110000 и SUM равно 22221111:

E:   00001110, 00001101, 00001011, 00000111

Этоприведет к C (8,3) × C (5,3) × C (8,1) × C (7,3) × C (4,3) = 56 × 10 × 8 × 35 × 4 = 627 200 решенийдля n = 8, m = 3, k = 5.

---

На самом деле, вам нужно добавить метод, чтобы не повторять один и тот же вектор и не рисовать себя в углу;так что я не думаю, что это будет проще, чем ответ Уолтера.

---

ПЕРВОНАЧАЛЬНЫЙ ОТВЕТ - ОСНОВНЫЕ ВОПРОСЫ

(я предполагаю, что m не больше n / 2, т. Е. Число единиц не больше, чем числонулей. В противном случае используйте симметричный подход.)

Когда k × m не больше n, очевидно, есть оптимальные решения, например:

n=10, m=3, k=3:  
A: 1110000000  
B: 0001110000  
C: 0000001110  

, где расстояния Хэммингавсе равны 2 × m:

|AB|=6, |AC|=6, |BC|=6, total=18

Когда k × m больше n, решения, в которых разница в расстояниях Хэмминга между последовательными векторами минимизирована, предлагают наибольшее общее расстояние:

n=8, m=3, k=4:
A: 11100000
B: 00111000
C: 00001110
D: 10000011
|AB|=4, |AC|=6, |AD|=4, |BC|=4, |BD|=6, |CD|=4, total=28  

n=8, m=3, k=4:
A: 11100000
B: 00011100
C: 00001110
D: 00000111
|AB|=6, |AC|=6, |AD|=6, |BC|=2, |BD|=4, |CD|=2, total=26  

Итак, практически, вы берете m × k и смотрите, насколько оно больше, чем n, назовем его x = m × k − n, а это x - число перекрытий, т. Е. Как часто будет вектородин в той же позиции, что и предыдущий вектор.Затем вы распределяете перекрытие между различными векторами как можно более равномерно, чтобы максимизировать общее расстояние.

В приведенном выше примере x = 3 × 4−8 = 4, и у нас есть 4 вектора, поэтому мы можем равномерно распределить перекрытие, и каждый вектор имеет 1 в том же положении, что и предыдущий вектор.

---

Чтобы сгенерировать все уникальные решения, вы можете:

• Рассчитать x = m × k − n и сгенерировать все разбиения x на k частей с наименьшим возможным максимумом.значение:

n=8, m=3, k=5  ->  x=7  
22111, 21211, 21121, 21112, 12211, 12121, 12112, 11221, 11212, 11122  
(discard partitions with value 3)  

• Генерировать все векторы, которые будут использоваться в качестве вектора A, например:

A: 11100000, 11010000, 11001000, 11000100, ... 00000111

• Для каждого из них сгенерироватьвсе векторы B, которые лексикографически меньше, чем вектор A, и имеют правильное количество перекрывающихся векторов A (в примере 1 и 2), например:

A: 10100100
overlap=1:  
B: 10011000, 10010010, 10010001, 10001010, 10001001, 10000011, 01110000, ... 00000111
overlap=2:  
B: 10100010, 10100001, 10010100, 10001100, 10000110, 10000101, 01100100, ... 00100101  

• Для каждого из них генерируйте все векторы C и так далее, пока у вас не будет наборов из k векторов.При генерации последнего вектора необходимо учитывать перекрытие с предыдущим, а также со следующим (т.е. первым) вектором.

---

Я предполагаю, что лучше всего рассматривать разбиения x на k как двоичное дерево:

                   1                                      2
      11                      12                    21         22
111        112           121       122        211       212    221
1112   1121   1122   1211   1212   1221   2111   2112   2121   2211
11122  11212  11221  12112  12121  12211  21112  21121  21211  22111

и обходить это дерево при создании решений, чтобы каждый векторнужно генерировать только один раз.

---

Я думаю, что этот метод работает только для некоторых значений n, m и k; Я не уверен, что это можно сделать для общего случая.

Answer 3

Может быть, вы найдете эту статью полезной (я ее написал).Он содержит алгоритмы, которые эффективно создают перестановки цепочек битов.

Например, алгоритм inc():

long  inc(long h_in , long m0 , long m1) {
    long  h_out = h_in | (~m1); //pre -mask
    h_out ++;
    // increment
    h_out = (h_out & m1) | m0; //post -mask
    return  h_out;
}

Он принимает входные данные h_in и возвращает следующее более высокое значение вминимум на 1 больше h_in и «соответствует» границам m0 и m1.«Соответствие» означает: результат имеет 1, где m0 имеет 1, а результат имеет 0, где m1 имеет 0.Не то чтобы h_in ДОЛЖЕН БЫТЬ действительным значением в отношении mo и m1!Кроме того, обратите внимание, что m0 должно быть побитовым меньше, чем m1, что означает, что m0 не может иметь 1 в позиции, где m1 имеет 0.

Это можетиспользоваться для генерации перестановок с минимальным расстоянием редактирования до заданной входной строки:

Давайте предположим, что у вас есть 0110, вы сначала ОТКАЗИТЕ его до 1001 (расстояние редактирования = k ),Установите «m0 = 1001» и «m1 = 1001».Использование этого приведет только к самому «1001».

Теперь, чтобы получить все значения с расстоянием редактирования k-1 , вы можете сделать следующее, просто перевернув один из битов m0 или m1, тогда inc() вернет упорядоченный ряд всех цепочек битов, которые имеют разницу k или k-1.

Я знаю, пока что это не очень интересно, но вы можете изменить до k бит, и inc() всегда будет возвращать все перестановки с максимально допустимой разницей в редактировании относительно m0 иm1.

Теперь, чтобы получить все перестановок, вам придется перезапустить алгоритм со всеми возможными комбинациями m0 и m1.

Пример: Комуполучить все возможные перестановки 0110 с расстоянием редактирования 2, вам нужно будет запустить inc () со следующими перестановками m0=0110 и m1=0110 (чтобы получить перестановки, битовая позиция должна быть расширена , что означает, что m0 установлено в 0, а m1 установлено в 1:

• Бит 0 и 1 расширенный : m0=0010и m1=1110
• Бит 0 и 2 расширенный : m0=0100 и m1=1110
• Бит 0 и 3 расширенный : m0=0110и m1=1111
• Бит 1 и 2 расширен : m0=0000 и m1=0110
• Бит 1 и 3 расширен : m0=0010и m1=0111
• Бит 2 и 3 расширенный : m0=0100 и m1=0111

В качестве начального значения для h_0 я предлагаю использовать простоm0. Итерация может быть прервана один раз inc() возвращает m1.

Сводка Приведенный выше алгоритм генерирует в O (x) все x двоичные векторы, которые отличаются не менее чем на y бит (настраивается) от заданного вектора v.

Используя ваше определение n = number of bits in a vector v, установка y=n генерирует ровно 1 вектор, который является полной противоположностью входного вектора v.Для y=n-1 он сгенерирует n+1 векторов: n векторов, которые различаются во всех, кроме одного бита, и 1 вектора, который отличается во всех битах.И так на разных значениях y.

** РЕДАКТИРОВАТЬ: Добавлено резюме и заменил ошибочный 'XOR' на 'NEGATE' в тексте выше.