部分摘要算法（PDP）

Question

我想實現部分摘要問題，該算法在第35-36頁的pdf https://cise.ufl.edu/class/cap5515sp10/Ch04_DNA_mapping.pdf中給出。在隨後的頁面中給出了一個例子。

我無法得到正確的答案。

我得到的X值是[0，10，8，3，6]，然後遞歸以「不好」停止。

可能是我不明白的算法或別的東西？

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

最後我的代碼運行正常，可能是我搞砸了python的全局空間或者一些幫助函數。

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)