Skip to main content
removeu 2625 caracteres do conteúdo
Fonte Link

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...

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...

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}

Obs.: Um algoritmo guloso não resolve todos os casos que preciso.

removeu 8 caracteres do conteúdo
Fonte Link
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)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)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
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) - 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) - 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
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
adicionou 8 caracteres ao conteúdo
Fonte Link
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**n2**(n+1) - 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**n2**(n+1) - 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
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
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) - 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) - 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
adicionou 568 caracteres ao conteúdo
Fonte Link
Carregando
adicionou 107 caracteres ao conteúdo
Fonte Link
Carregando
adicionou 617 caracteres ao conteúdo
Fonte Link
Carregando
nova tag
Link
ederwander
  • 6,6mil
  • 24
  • 32
Carregando
adicionou 1059 caracteres ao conteúdo
Fonte Link
Carregando
conteúdo editado
Fonte Link
Carregando
adicionou 160 caracteres ao conteúdo
Fonte Link
Carregando
Fonte Link
Carregando