問題描述
這應(yīng)該是一個(gè)常見問題。有兩個(gè)隊(duì)列忍级，A與B帆谍，A隊(duì)列中元素與B隊(duì)列中元素存在匹配關(guān)系，匹配時(shí)需要保持順序關(guān)系轴咱，例如A隊(duì)列中兩個(gè)元素A1汛蝙，A2烈涮，與B隊(duì)列的B1，B2可以進(jìn)行匹配窖剑，但如果B隊(duì)列元素順序?yàn)锽2坚洽，B1，那么或者A1與B1匹配西土，或者A2與B2匹配讶舰，不能兩個(gè)元素都匹配。
假設(shè)需了，An與Bn匹配跳昼，n數(shù)字相同就能匹配，例如前例中提及的A1肋乍、B1庐舟。對于兩個(gè)序列，A1住拭，A2，A3與B2历帚，B3滔岳，B1，最大匹配是多少挽牢？正確答案是2谱煤，即，A2與B2禽拔，A3于B3進(jìn)行匹配刘离，A1于B1不進(jìn)行匹配。
了解了問題場景后睹栖，那么問題來了硫惕，對于兩個(gè)序列來說，最大匹配元素個(gè)數(shù)是多少野来？
算法實(shí)現(xiàn)
思路
問題的核心在于恼除，如何知道哪個(gè)元素應(yīng)該匹配還是應(yīng)該被放棄匹配。尋找最大匹配個(gè)數(shù)的關(guān)鍵在于曼氛，逆向找出每個(gè)元素的最大匹配數(shù)豁辉。
- 首先，用A序列最后元素在B序列中逆向查詢匹配項(xiàng)舀患，并標(biāo)記最大匹配為1徽级，并按匹配位置，將B序列切分為兩個(gè)子序列聊浅，BX1（匹配點(diǎn)前序列）餐抢，BX2（匹配點(diǎn)后序列）现使；
- 然后，用前一個(gè)元素逆向分別在BX1弹澎，BX2兩個(gè)序列上逆向進(jìn)行匹配朴下，如果找到匹配項(xiàng)，則標(biāo)記BX1序列上的匹配點(diǎn)最大匹配為2苦蒿，BX2序列上的匹配點(diǎn)最大匹配為1,并將B序列切分為BX1（最大匹配2前序列）殴胧，BX2（最大匹配1前序列），BX3子序列（最大匹配1后序列）佩迟，核心是將B序列切分為不同等級的子序列团滥；
- 最后，依次對前一個(gè)元素分別進(jìn)行步驟2报强。
拿前章節(jié)例子來說灸姊，首先，用A3在B隊(duì)列中進(jìn)行匹配秉溉，找到第二個(gè)元素B3力惯，標(biāo)記該元素最大匹配為1，切分B隊(duì)列為[B[1],B[2]]召嘶、[B[3]]父晶，然后，對A2進(jìn)行不同隊(duì)列下的匹配弄跌，在第一個(gè)隊(duì)列中甲喝，找到匹配項(xiàng)B2，標(biāo)記該匹配最大匹配值為2铛只，切分隊(duì)列為[B[1]],[B[2]],[B[3]]埠胖，最后，對A1進(jìn)行不同隊(duì)列下匹配淳玩，再[B[3]]隊(duì)列中找到匹配項(xiàng)B1,標(biāo)記該匹配最大匹配為1,對各個(gè)隊(duì)列進(jìn)行最大匹配統(tǒng)計(jì)直撤，發(fā)現(xiàn)[B[1]]隊(duì)列最大匹配最大，為2凯肋。
算法實(shí)現(xiàn)
算法實(shí)現(xiàn)與上述算法描述有所區(qū)別谊惭，主要是沒有進(jìn)行子隊(duì)列切分。子隊(duì)列切分侮东，主要目的是為了減少匹配次數(shù)圈盔，對算法核心原理并沒有影響。
def flag_max_match(item, b_list, b_max_match):
# Find match item from end of b_list to begin
# default max_match = 0
cur_max_match = 0
for i in range(len(b_list)-1, -1, -1):
if item == b_list[i]:
if cur_max_match+1>b_max_match[i]['max']:
b_max_match[i]['max'] = cur_max_match+1
b_max_match[i]['item'] = 'A'+str(item)
continue
cur_max_match = b_max_match[i]['max'] if b_max_match[i]['max']>cur_max_match else cur_max_match
def flag_max_matchs(a_list, b_list, b_max_match):
for i in range(len(a_list)-1, -1, -1):
flag_max_match(a_list[i], b_list, b_max_match)
print('match itme:',a_list[i], 'match result:', b_max_match)
max_match = 0
for t_max in b_max_match:
max_match = t_max['max'] if t_max['max']>max_match else max_match
return max_match
def find_max_matchs(a_list, b_list):
b_max_match = []
for i in range(0, len(b_list)):
b_max_match.append({'item':'', 'max':0})
max_match = flag_max_matchs(a_list, b_list, b_max_match)
return (max_match, b_max_match)
# Test
a_list = [2,3,1]
b_list = [1,2,3]
print(find_max_matchs(a_list, b_list))
輸出結(jié)果如下：
match itme: 1 match result: [{'item': 'A1', 'max': 1}, {'item': '', 'max': 0}, {'item': '', 'max': 0}]
match itme: 3 match result: [{'item': 'A1', 'max': 1}, {'item': '', 'max': 0}, {'item': 'A3', 'max': 1}]
match itme: 2 match result: [{'item': 'A1', 'max': 1}, {'item': 'A2', 'max': 2}, {'item': 'A3', 'max': 1}]
(2, [{'item': 'A1', 'max': 1}, {'item': 'A2', 'max': 2}, {'item': 'A3', 'max': 1}])
從代碼實(shí)現(xiàn)層面對源碼進(jìn)行優(yōu)化悄雅，讓代碼更優(yōu)美驱敲，易讀，整個(gè)算法實(shí)現(xiàn)大概11行代碼宽闲。優(yōu)化后代碼如下：
def flag_max_match(item, b_list, b_max_match):
# Find match item from end of b_list to begin
# default max_match = 0
cur_max_match = 0
for i in range(len(b_list)-1, -1, -1):
if item == b_list[i] and cur_max_match+1>b_max_match[i]['max']:
# update b_max_match list
b_max_match[i] = {'max': cur_max_match+1, 'item': 'A'+str(item)}
else:
# update current max_match visited
cur_max_match = b_max_match[i]['max'] if b_max_match[i]['max']>cur_max_match else cur_max_match
def flag_max_matchs(a_list, b_list):
b_max_match = [{'item':'', 'max':0} for i in range(len(b_list))]
[flag_max_match(item, b_list, b_max_match) for item in a_list[::-1]]
return (max([item['max'] for item in b_max_match]), b_max_match)
# Test
a_list = [2,3,1]
b_list = [1,2,3]
print(flag_max_matchs(a_list, b_list))
代碼倉庫：https://gitee.com/imlaji/max_match/blob/master/max_match.py
