部分摘要算法(PDP)

Question

我正在尝试实现部分摘要问题，算法在35-36页的pdf https://cise.ufl.edu/class/cap5515sp10/Ch04_DNA_mapping.pdf中给出。后面几页给出了一个例子。

我无法得到正确的答案。

我得到的X的值是0，10，8，3，6，然后递归以"Not ok“结束。

可能是我不理解算法还是别的什么？

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)