※ 引述《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 结构。