Backtracking in Python

Asked

Viewed 555 times

2

I’m trying to find a subset, of size M, of binary strings of length n, where any string has a distance greater than 2 for any other string in the subset.

Where the distance between two strings is the number of positions where they differ. For example, the distance between 101 and 011 is 2.

Example: {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}

A subset with 3 elements with distance > 2 would be {00000,00111,11001}. Suppose that with this choice, I cannot add any more elements to the subset. I want the program to remove the last placed element, 01011, and put the next one that has dist > 2 to 00000 and 00111, in case, 11001. Then the subset would be {00000,00111,11010}. And he would be able to add one more element, which would be 11101.

And give me the subset {00000,00111,11010,11101}.

This is a difficult problem. But I need to solve for small cases, so a brute force program is enough.

Note: A greedy algorithm does not solve all the cases I need.

python algorithm
  • 1

    Hi. Welcome to SOPT. Your question is somewhat difficult to answer because you don’t explain your code and what it does is also somewhat vague. You talk about a set of strings, but you don’t exemplify or illustrate the strings. You say you "don’t get an answer," but what would be the expected answer? Anyway, it’s hard for anyone to even be interested in helping you. I suggest you read [Ask] and edit your question to explain exactly what your difficulty is. If the problem is wide, break it into smaller pieces (you can open more than one question here).

  • I tried hard to understand your problem, but it’s not very clear what you’re trying to do, at first your problem seems to be related to the Levenshtein Distance, but it’s just a hunch...

  • Thanks, I tried to explain better. The program must be very bad, I know almost nothing of python, sorry, rs

  • "A subset with 3 elements with distance > 2 would be {00000,00111,01011}". No, it wouldn’t be, because the distance between "00111" and "01011" is 2.

  • @Luizvieira removed my answer, the last edition left me more confused about the actual functioning of the algorithm, as far as I had understood, she seemed to be comparing the first element with the others, and was doing this successively until comparing all, unfortunately it’s not yet clear to me, maybe someone else with more patience.

  • Yes, indeed, the example was wrong. Thank you. Only need a set where any element has distance > 2 for any other element of the set =/ Rs

Show 1 more comment

1 answer

2


I made it, thank you all!

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)

Browser other questions tagged python algorithm

You are not signed in. Login or sign up in order to post.