Estou tentando encontrar um subconjunto, de tamanho M, de strings binárias de comprimento n, onde qualquer string tenha distância maior que 2 para qualquer outra string do subconjunto.
Onde a distância entre duas strings é o número de posições onde elas diferem. Por exemplo, a distância entre 101 e 011 é 2.
Exemplo: {00000,00001,00010,00011,00100,00101,00110,00111,01000,01001,01010,01011,01100,01101,01110,01111,10000,10001,10010,10011,10100,10101,10110,10111,11000,11001,11010,11011,11100,11101,11110,11111}
Um subconjunto com 3 elementos com distância > 2 seria {00000,00111,11001}. Suponha que com essa escolha, não consigo adicionar mais nenhum elemento ao subconjunto. Quero que o programa retire o último elemento colocado, 01011, e coloque o próximo que tem dist > 2 para 00000 e 00111, no caso, 11001. Então o subconjunto ficaria {00000,00111,11010}. E ele conseguiria adicionar mais um elemento, que seria 11101.
E me daria o subconjunto {00000,00111,11010,11101}.
Esse é um problema difícil. Mas preciso resolver para uns casos pequenos, então um programa de força bruta me basta.
Obs.: Um algoritmo guloso não resolve todos os casos que preciso.