作者liataian (T-PANY FOREVER)
看板Python
标题[问题] pattern比对的问题
时间Mon Oct 13 21:55:27 2014
大家好, 有一个问题让我百思不得其解, 想上来请教一下板友的想法
假设我现在有一个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://webptt.com/cn.aspx?n=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
1F：推 ocean5566: import re? 10/13 22:19
2F：→ liataian: 海洋56大, 我有想到regex, 可是对於这种动态的完全不知 10/13 22:23
3F：→ liataian: 如何下手... 10/13 22:23
4F：推 eight0: 先把单字元去掉，剩下的当作边，画图，拔掉捷径。O(n)的样 10/13 23:03
5F：→ eight0: 子 10/13 23:03
6F：推 ckc1ark: topological sort吗 10/13 23:20
7F：→ liataian: 感谢楼上e大跟c大提点, 我尝试往这个方向做做看 10/13 23:26
8F：→ liataian: 如有别的方法还请不吝指教~ 10/13 23:28
9F：推 darkgerm: 感觉是个 FSM 转 regular 的应用XD 10/14 00:21
10F：→ liataian: 嗯..感觉会牵扯到比较复杂的运算..XD 10/14 00:43