问题描述
这应该是一个常见问题。有两个队列，A与B，A队列中元素与B队列中元素存在匹配关系，匹配时需要保持顺序关系，例如A队列中两个元素A1，A2，与B队列的B1，B2可以进行匹配，但如果B队列元素顺序为B2，B1，那么或者A1与B1匹配，或者A2与B2匹配，不能两个元素都匹配。
假设，An与Bn匹配，n数字相同就能匹配，例如前例中提及的A1、B1。对于两个序列，A1，A2，A3与B2，B3，B1，最大匹配是多少？正确答案是2，即，A2与B2，A3于B3进行匹配，A1于B1不进行匹配。
了解了问题场景后，那么问题来了，对于两个序列来说，最大匹配元素个数是多少？
算法实现
思路
问题的核心在于，如何知道哪个元素应该匹配还是应该被放弃匹配。寻找最大匹配个数的关键在于，逆向找出每个元素的最大匹配数。
- 首先，用A序列最后元素在B序列中逆向查询匹配项，并标记最大匹配为1，并按匹配位置，将B序列切分为两个子序列，BX1（匹配点前序列），BX2（匹配点后序列）；
- 然后，用前一个元素逆向分别在BX1，BX2两个序列上逆向进行匹配，如果找到匹配项，则标记BX1序列上的匹配点最大匹配为2，BX2序列上的匹配点最大匹配为1,并将B序列切分为BX1（最大匹配2前序列），BX2（最大匹配1前序列），BX3子序列（最大匹配1后序列），核心是将B序列切分为不同等级的子序列；
- 最后，依次对前一个元素分别进行步骤2。
拿前章节例子来说，首先，用A3在B队列中进行匹配，找到第二个元素B3，标记该元素最大匹配为1，切分B队列为[B[1],B[2]]、[B[3]]，然后，对A2进行不同队列下的匹配，在第一个队列中，找到匹配项B2，标记该匹配最大匹配值为2，切分队列为[B[1]],[B[2]],[B[3]]，最后，对A1进行不同队列下匹配，再[B[3]]队列中找到匹配项B1,标记该匹配最大匹配为1,对各个队列进行最大匹配统计，发现[B[1]]队列最大匹配最大，为2。
算法实现
算法实现与上述算法描述有所区别，主要是没有进行子队列切分。子队列切分，主要目的是为了减少匹配次数，对算法核心原理并没有影响。
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))
输出结果如下：
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}])
从代码实现层面对源码进行优化，让代码更优美，易读，整个算法实现大概11行代码。优化后代码如下：
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
网友评论