Backtracking in Python

Question

Backtracking in Python

Navigation

#1 by (2 votes)

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,01,000,01001,01010,01011,01100,01101,01110,01111,10000,10001,10010,10011,10100,10101,10110,10111,11,000 , 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 can not add any more elements to the subset. I want the program to remove the last element placed, 01011, and put the next one that has dist > 2 to 00000 and 00111, in this case, 11001. Then the subset would be {00000,00111,11010}. And he could add another element, which would be 11101.

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

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

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

algoritmo python

asked by anonymous 24.02.2017 / 21:09

1 answer

How to clean / reset bootstrap fileinput after selecting new image? Python Interpolate Txt

score 2 · Accepted Answer

I did 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)