[問題] pattern比對的問題

[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)

想請教板友有什麼工具可以達成我要的目的嗎?

或是板友有什麼想法可以提供嗎?

感覺自己描述得不太好, 如果有不清楚還請見諒@@

謝謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.73.233.198
※ 文章網址: http://www.ptt.cc/bbs/Python/M.1413208533.A.60D.html
※ 編輯: liataian (203.73.233.198), 10/13/2014 21:56:24
※ 編輯: liataian (203.73.233.198), 10/13/2014 22:01:41
※ 編輯: liataian (203.73.233.198), 10/13/2014 22:04:42
※ 編輯: liataian (203.73.233.198), 10/13/2014 22:21:15
推 ocean5566: import re?
→ liataian: 海洋56大, 我有想到regex, 可是對於這種動態的完全不知
→ liataian: 如何下手...
推 eight0: 先把單字元去掉，剩下的當作邊，畫圖，拔掉捷徑。O(n)的樣
→ eight0: 子
推 ckc1ark: topological sort嗎
→ liataian: 感謝樓上e大跟c大提點, 我嘗試往這個方向做做看
→ liataian: 如有別的方法還請不吝指教~
推 darkgerm: 感覺是個 FSM 轉 regular 的應用XD
→ liataian: 嗯..感覺會牽扯到比較複雜的運算..XD