[問題] 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