Partial Digest Algorithm (PDP)

Question

Ich versuche, das partielle Digest Problem zu implementieren, der Algorithmus ist in dieser pdf https://cise.ufl.edu/class/cap5515sp10/Ch04_DNA_mapping.pdf auf den Seiten 35-36 gegeben. Auf den folgenden Seiten finden Sie ein Beispiel.

Ich bin nicht in der Lage, die richtige Antwort zu bekommen.

Der Wert von X, den ich bekomme, ist [0, 10, 8, 3, 6] und dann stoppt die Rekursion mit "Nicht ok".

Kann ich den Algorithmus oder etwas anderes nicht verstehen?

width = 0 

def partialDigest(L): 
    print "partialDigest" 
    global width 
    width = max(L) 
    L.remove(width) 
    X = [0, width] 
    if place(L, X): 
     print "Ok" 
    else: 
     print "Not ok" 


def place(L, X): 
    print "place" 
    print "Width is", width 
    print "L is ", L 
    print "X is ", X 

    if len(L) == 0: 
     print "Output is: ", X 
     return True 

    y = max(L) 
    print "Y is", y 
    #L.remove(y) 
    d = D(y, X) 
    print "d is ", d 

    if set(d).issubset(set(L)): 
     print "First if" 
     print "D is", d 
     print "X before is ", X 
     X.append(y) 
     print "X after is ", X 
     print "L before is", L 
     L = removeElements(d, L) 
     print "L after is ", L 
     place(L, X) 
     X.remove(y) 
     L.extend(d) 

    d1 = D(abs(width-y), X) 
    print "d1 is ", d1 

    if set(d1).issubset(set(L)): 
     print "Second if" 
     print "D is", d1 
     print "X before is ", X 
     X.append(abs(width-y)) 
     print "X after is ", X 
     print "L before is", L 
     L = removeElements(d1, L) 
     print "L after is ", L 
     place(L, X) 
     X.remove(abs(width-y)) 
     L.extend(d1) 

    return False 

def D(y, X): 
    diff = [] 
    for xi in X: 
     diff.append(abs(y-xi)) 
    return diff 

def removeElements(d, L): 
    for i in L: 
     for j in d: 
      if i == j: 
       L.remove(i) 
       d.remove(i) 
    return L 

if __name__ == "__main__": 
    print "Python implementation of partial digetive problem PDP on page 90." 

    partialDigest([2, 2, 3, 3, 4, 5, 6, 7, 8, 10]) 

Answer 1

Endlich habe ich den Code korrekt ausgeführt wird, vermasselt Ich war der Python den globalen Raum oder eine Hilfsfunktion kann.

X = [] 

L = [2, 2, 3, 3, 4, 5, 6, 7, 8, 10] 

width = 0 

def partialDigest(L): 
    global X, width 
    width = max(L) 
    L.remove(width) 
    X = [0, width] 
    place(L, X) 


def place(L, X): 

    if not L: 
     print "Output is: ", X 
     return 

    y = max(L) 

    if issubset(y, X, L): 
     X.append(y) 
     removeElements(y, X, L) 
     place(L, X) 
     if y in X: 
      X.remove(y) 
     L.extend(D(y, X)) 

    if issubset(abs(width-y), X, L): 
     X.append(abs(width-y)) 
     removeElements(abs(width-y), X, L) 
     place(L, X) 
     if abs(width-y) in X: 
      X.remove(abs(width-y)) 
     L.extend(D(abs(width-y), X)) 

    return 


def D(y, X): 
    diff = [] 
    for xi in X: 
     diff.append(abs(y-xi)) 
    return diff 


def removeElements(y, X, L): 
    for xi in X: 
     if abs(y - xi) in L: 
      L.remove(abs(y - xi)) 


def issubset(y, X, L): 
     for xi in X: 
      if abs(y-xi) not in L: 
       return False 
     return True 


if __name__ == "__main__": 
    print "Python implementation of partial digetive problem PDP on page 90." 

    partialDigest(L)