A função distância que fiz, pode não ser a mais eficiente, mas ela está funcionando bem. O meu problema é fazer a parte do backtracking, pois um algoritmo guloso, nem sempre me dá o resultado esperado.
Faço a busca em ordem numérica.
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}
(Estou engatinhando, na verdade, quero encontrar o maior conjunto possível).
def dist(a,b): %tomo a e b na base decimal k = 0 for i in range (0,5): %considero números com no máximo 5 bits em sua representação binária if a%2 != b%2: %faço a divisão de a e b por 2 e vejo se os restos são distintos k = k + 1 a = a/2 b = b/2 return k
def bin(n): %dá a representação binária de um número n decimal nd = 0 pot = 1 while (n > 0): nd = nd + n%2 * pot n = n/2 pot = pot * 10 return nd
o = [] %guardo os números que entram no subconjunto o = o + [0] %o primeiro deles vai ser o 0 count = 0 j = 0 M = 40 n = 9 Tam = 2**n - 1
while count < M: %quero encontrar mais 39 elementos (o 00...0 vai estar no subconjunto, s.p.g) aux = 0 for i in range (0,len(o)): if dist(o[i],j+1) > 2: %testa se j+1 tem dist > 2 para **cada** elemento do subconjunto aux += 1 if aux == len(o): %se j+1 tem dist > 2 para todos os elementos de o o.append(j+1) %então j+1 entra no subconjunto count += 1 %conta quantos elementos entraram no subconjunto ult = j+1 %salva o último elemento que entrou no subconjunto j +=1 else: j+=1 if j == Tam: %testo apenas o números de 1 a 2**n - 1 (pois têm até n bits na representação binária) if count > M-2: %se o subconjunto tem mais M-1 elementos, imprime for i in range (0,len(o)): print bin(o[i]) print count else: o.pop() %se não tem M-1 elementos, retiro o último elemento que entrou no subconjunto e tenta colocar o próximo candidato do lugar deste j = ult
Obs.: Um algoritmo guloso não resolve todos os casos que preciso. O meu algoritmo funciona quando testo os casos n = 5, M = 4; n = 6, M = 8; n = 7, M = 16; e n = 8, M = 20 (Esses valores de M são provados serem ótimos http://www.win.tue.nl/~aeb/codes/binary-1.html). Para o caso de n = 9, M = 40, coloco para rodar e meu programa não faz nada. Acredito que neste caso o subconjunto não possa ser encontrado de maneira gulosa. Essa parte de tirar elementos escolhidos do subconjuntos e tentar com novas escolhas, acho que está feita de maneira errada no meu código...