2

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.

6
  • 1
    Olá. Bem vinda ao SOPT. A sua pergunta é um tanto difícil de ser respondida porque você não explica o seu código e o que ele faz também é um tanto vago. Vc fala de conjunto de strings, mas não exemplifica nem ilustra as strings. Diz que "não obtém resposta", mas qual seria a resposta esperada? Enfim, fica difícil de alguém sequer se interessar em te ajudar. Sugiro que leia Como perguntar e edite a sua pergunta para explicar qual exatamente é a sua dificuldade. Se o problema for amplo, quebre-o em pedaços menores (vc pode abrir mais de uma pergunta por aqui). Commented 24/02/2017 às 22:37
  • Me esforcei pra entender o seu problema, mas não ficou muito claro o que você está tentando fazer, a principio o seu problema parece estar relacionado com a Distância Levenshtein, mas é apenas um palpite...
    – ederwander
    Commented 24/02/2017 às 22:59
  • Obrigada, tentei explicar melhor. O programa deve estar bem ruim, não sei quase nada de python, desculpem, rs
    – Natália
    Commented 24/02/2017 às 23:42
  • "Um subconjunto com 3 elementos com distância > 2 seria {00000,00111,01011}". Não, não seria, porque a distância entre "00111" e "01011" é 2. Commented 25/02/2017 às 19:36
  • @LuizVieira removi minha resposta, a ultima edição me deixou mais confuso sobre o real funcionamento do algoritmo, até onde eu tinha entendido, ela parecia estar comparando o primeiro elemento com os demais, e ia fazendo isso sucessivamente até comparar todos, infelizmente ainda não ficou claro pra mim, talvez outra pessoa com mais paciência desvende o enigma lol.
    – ederwander
    Commented 25/02/2017 às 22:16

1 Resposta 1

2

Consegui fazer, obrigada a todos!

def dist(a,b):
    k = 0 
    for i in range (0,20):
        if a%2 != b%2:
            k = k + 1
        a = a/2
        b = b/2 
    return k 

def bin(n):
    nd = 0
    pot = 1
    while (n > 0):
        nd = nd + n%2 * pot
        n = n/2
        pot = pot * 10
    return nd

o = []
o = o + [0]
M = 4
n = 5
d = 3
Tam = 2**n - 1

def cod(ult):
    j = ult
    while j < Tam+1: 
        aux = 0
        for i in range (0,len(o)): 
            if dist(o[i],j+1) > d-1: 
            aux += 1 
        if aux == len(o): 
            o.append(j+1) 
            j +=1
        else:
            j+=1
    return (o)   

cod(0)

while len(o) < M+1:
    if len(o) > M-1:
        for i in range (0,len(o)):
            print bin(o[i])
        print o
        print len(o)
        break
    else:
        ult = o.pop() 
        cod(ult)

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .