※ 引述《liataian (T-PANY FOREVER)》之铭言： : 大家好, 有一个问题让我百思不得其解, 想上来请教一下板友的想法 : 假设我现在有一个list = ['AB','B','AC','CD','E'] : 我想要对list中的元素train一个有关前後顺序的pattern : 以上例来说, 每次train出的pattern如下(在[]中的字母是有顺序的, 在{}中则无): : 'AB' 跟 'B' 比对後train出一个pattern1 : [A,B] (得知A在B前面) : pattern1 跟 'AC' 比对後再train出一个pattern2 : [A,{B,C}] (得知A也在C前面) : pattern2 跟 'CD' 比对後再train出一个pattern3 : [A,{B,[C,D]}] (得知A也在D前面, : 且C在D前面) : pattern3 跟 'E' 比对後再train出一个pattern4 : {[A,{B,[C,D]}],E} : 最後我可以知道的结果就是: "A一定在B,C,D前面, C一定在D前面" : 其他可能还不知道先後顺序的部分先不管(因为这个list之後会再加入更多item去train) : 想请教板友有什麽工具可以达成我要的目的吗? : 或是板友有什麽想法可以提供吗? : 感觉自己描述得不太好, 如果有不清楚还请见谅@@ : 谢谢 基本的工具是一些演算法。 第一步，做字典排序。用意是尽可能由前往後，不需要回溯太多种情况。例如， 以下四个字串经过字典排序之後，是以下四个字串的顺序。 a de b de c c e 第二步，要用 maximal common sequence 演算法。 ade 和 bde 做 MCS 之後， 分别会分解为 [a,de,empty] 和 [b,de,empty] ， de 是共有的部分。而前後为 差异的部分。差异的部分合并，并且保持先後顺序，就合并为 [{a,b},de] 。 再往後算，就应该是要对现有的结构的每一项， a, b, de 等等，个别算有没有 MCS ，如果有，就表示在 [{a,b},de] 中可以拉一条分歧线出来。如果下一项 进来都没有 MCS ，就是对现有的 graph 来说完全独立的东西。 用这种方法一直算，就会是这样： MCS(ade, bde) => [{a,b},de,{empty,empty}] => [{a,b},de] MCS([{a,b},de], c) => {[{a,b},de],c} MCS({[{a,b},de],c}, ce) => {[{a,b},{d,c},e,{empty,empty}], [{empty,empty},c,{empty,e}]} => {[{a,b},{d,c},e],ce} 不过这样出现重叠的路线 ce 了，就需要加一个去除重复的步骤。 我觉得，去除重复的基础，应该是你所提的 pattern1 的产生， 因为 B 对於 AB 来说可以融合，所以 B 消失了。 这个基础式子是以下几条规则： {ab,b} => MCS(ab,b) => [{a,empty},b,{empty,empty}] => ab {a,b} => MCS(a,b) => {a,b} {empty,a} => a {a,empty} => a {empty,empty} => [] 所以当 {[{a,b},{d,c},e],ce} 出现时，要做 MCS([{a,b},{d,c},e], ce) ， 意思就是在设计 MCS 函数时，要想到该怎麽处理各种 graph 结构。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.160.159.130 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Python/M.1413221250.A.882.html