[问题] pattern比对的问题

楼主: liataian (T-PANY FOREVER)   2014-10-13 21:55:27
大家好, 有一个问题让我百思不得其解, 想上来请教一下板友的想法
假设我现在有一个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)
想请教板友有什么工具可以达成我要的目的吗?
或是板友有什么想法可以提供吗?
感觉自己描述得不太好, 如果有不清楚还请见谅@@
谢谢
作者: ocean5566 (煙大屌熟男)   2014-10-13 22:19:00
import re?
楼主: liataian (T-PANY FOREVER)   2014-10-13 22:23:00
海洋56大, 我有想到regex, 可是对于这种动态的完全不知如何下手...
作者: eight0 (欸XD)   2014-10-13 23:03:00
先把单字符去掉,剩下的当作边,画图,拔掉捷径。O(n)的样子
作者: ckc1ark (伪物)   2014-10-13 23:20:00
topological sort吗
楼主: liataian (T-PANY FOREVER)   2014-10-13 23:26:00
感谢楼上e大跟c大提点, 我尝试往这个方向做做看如有别的方法还请不吝指教~
作者: darkgerm (黑骏)   2014-10-14 00:21:00
感觉是个 FSM 转 regular 的应用XD
楼主: liataian (T-PANY FOREVER)   2014-10-14 00:43:00
嗯..感觉会牵扯到比较复杂的运算..XD

Links booklink

Contact Us: admin [ a t ] ucptt.com