多最长公共子序列

Question

算法正确吗？好像很管用。

print("Multiple sequence longest common subsequence implementation in Python.\nFor example a naive algorithm would perfom c*128^128 elementary operations on a problem set of 128 sequences of length 128 elements.")
print(" That is: ", 128**128, "operations.")

from collections import defaultdict
import sys

def ptable(m, n, table):
   for i in range(m):
       line = ""
       for j in range(n):
           line += str(table[i, j]) + " "
       print(line)

def lcs(x, y):
    table = defaultdict(int)
    n = len(x)
    m = len(y)

    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                table[i, j] = table[i-1, j-1]+1
            else:
                table[i, j] = max(table[i-1, j], table[i, j-1])

    return table

def mlcs(strings):
    strings = list(set(strings))
    tables = dict()
    for i in range(1, len(strings)):
        x = strings[i]
        for y in strings[:i]:
            lcsxy = lcs(x, y)
            tables[x,y] = lcsxy

    def rec(indexes):
        for v in indexes.values():
            if v < 0:
                return ""
        same = True
        for i in range(len(strings)-1):
            x = strings[i]
            y = strings[i+1]
            same &= x[indexes[x]] == y[indexes[y]]
        if same:
            x = strings[0]
            c = x[indexes[x]]
            for x in strings:
                indexes[x] -= 1
            return rec(indexes) + c
        else:
            v = -1
            ind = None
            for x in strings:
                indcopy = indexes.copy()
                indcopy[x] -= 1
                icv = valueat(indcopy)
                if icv > v:
                    ind = indcopy
                    v = icv
            indexes = ind
            return rec(indexes)

    def valueat(indexes):
        m = 12777216
        for i in range(1, len(strings)):
            x = strings[i]
            for y in strings[:i]:
                lcsxy = tables[x,y]
                p = lcsxy[indexes[x],indexes[y]]
                m = min(m, p)
        return m         

    indexes = dict()
    for x in strings:
        indexes[x] = len(x) - 1
    return rec(indexes)

def check(string, seq):
    i = 0
    j = 0
    while i < len(string) and j < len(seq):
        if string[i] == seq[j]:
            j += 1
        i += 1
    return len(seq) - j

def checkall(strings, seq):
    for x in strings:
        a = check(x, seq)
        if not a == 0:
            print(x, seq, a)
            return False
    return True

strings = []
sigma = ["a", "b", "c", "d"]
#sigma = ["a", "b"]
import random
for i in range(5):    
    string = ""
    for j in range(128):
        string += random.choice(sigma)
    strings += [string]

#strings = ["abbab", "ababa", "abbba"]
#strings = ["abab", "baba", "abaa"]
#strings = ["bacda", "abcde", "decac"]
#strings = ["babbabbb", "bbbaabaa", "abbbabab", "abbababa"]
#strings = ["human", "chimpanzee", "woman"]
#strings = ["ababa", "babab", "bbbab"]
#strings = ["ababaaba", "abbabbaa", "aaaaabba"]
#strings = ["aabbbaba", "aaaabbba", "aabbbaab"]
print("Strings:", strings)
l = mlcs(strings)
print("Lcs:", l, checkall(strings, l))`

Answer 1

这种测试用例生成方法产生结果有时次优的情况。因此，该算法存在一个缺陷。

strings = []
sigma = ["a", "b", "c", "d"]
#sigma = ["a", "b"]
sigmax = ["e", " f", "g"]
import random
Nx = 8
N = 16
M = 5 # Number of strings
x = ""
for i in range(Nx):
    x += random.choice(sigmax)
for i in range(M):    
    string = ""
    for j in range(N):
        string += random.choice(sigma)
    indexes = list(range(N))
    random.shuffle(indexes)
    indexes = sorted(indexes[:len(x)])
    for j in range(len(x)):
        string = string[:indexes[j]]+x[j]+string[indexes[j]:]
    strings += [string]

所以，回到画板上，可以这么说。