我已将问题拆分为子问题...检查它的测试都按预期工作：
# These are the two lists I want to pair
a = [ "apples"
, "oranges"
, "bananas"
, "blueberries" ]
b = [ "apples"
, "blueberries"
, "oranges"
, "bananas" ]
# This is the expected result
expected = [ (0, 0)
, (None, 1)
, (1, 2)
, (2, 3)
, (3, None) ]
# Test the function gets the correct result
assert expected == get_indexes_for_best_pairing(a, b)
print("Tests pass!")
1. 创建所有对的列表
使用关联索引列表创建列表 A 中的值的映射...
def map_list(list):
map = {}
for i in range(0, len(list)):
# Each element could be contained multiple times in each
# list, therefore we need to create a sub array of indices
if not list[i] in map:
map[list[i]] = []
# Add the index onto this sub array
map[list[i]].append(i)
return map
看起来map像...
{ "apples": [0]
, "oranges": [1]
, "bananas": [2]
, "blueberries": [3] }
通过交叉引用列表 B 查找所有对...
def get_pairs(a, b):
map = map_list(a)
pairs = []
for i in range(0, len(b)):
v = b[i]
if v in map:
for j in range(0, len(map[v])):
pairs.append((map[v][j], i))
return pairs
具体pairs如下...
[ (0, 0)
, (3, 1)
, (1, 2)
, (2, 3) ]
2. 获取每对的分数
只需循环遍历这些对并在原始列表中查找值：
def get_pairs_scores(pairs, a):
return [len(a[i]) for i, _ in pairs]
3.创建每对排除的对列表
对于每一对找到它排除的其他对...
def get_pairs_excluded_by_pair(pairs, i):
# Check if the context pair excludes the pair, if both of the
# pairs indexes are greater or less than the other pair, then
# the pairs are inclusive and we will have a positive number,
# otherwise it will be negative
return [j for j in range(0, len(pairs))
# If the current context pair is also the pair we are comparing
# skip to the next pair
if i != j
and ((pairs[i][0] - pairs[j][0]) * (pairs[i][1] - pairs[j][1]) < 0)]
def get_pairs_excluded_by_pairs(pairs):
excludes = []
for i in range(0, len(pairs)):
excludes.append(get_pairs_excluded_by_pair(pairs, i))
return excludes
该pairs_excludes方法将返回...
[ []
, [2, 3]
, [1]
, [1] ]
4. 计算每对的总累积分数减去它排除的对
加上它排除的对排除的对的分数......等等。
使用深度优先算法遍历排除的非循环图以获得每对的累积分数......这是我们需要做的事情......
def get_cumulative_scores_for_pairs(pairs, excludes, scores):
cumulative = []
# For each pair referenced in the excludes structure we create a new
# graph which starting from that pair. This graph tells us the total
# cumulative score for that pair
for i in range(0, len(pairs)):
score = 0
# Keep a reference of the nodes that have already been checked by
# in this graph using a set. This makes the graph acyclic
checked = set()
checked.add(i)
# We keep a note of where we are in the graph using this trail
# The pairs relate to the index in the pair_excludes. if pair
# first is x and pair second is y it refers to pair_excludes[x][y]
trail = []
# We start the current x, y to be the first exclude of the current
# start node
current = [i, 0]
# Sorry, tree traversal... Might not very readable could
# be done with recursion if that is your flavour
while True:
# Get the referenced excluded node
if len(excludes[current[0]]) > current[1]:
j = excludes[current[0]][current[1]]
# We do not want to calculate the same pair twice
if not j in checked:
# It has not been checked so we move our focus to
# this pair so we can examine its excludes
trail.append(current)
# We mark the pair as checked so that we do
# not try and focus on it if it turns up again
checked.add(j)
current = [j, 0]
# We perform a trick here, where when we traverse
# down or up a layer we flip the sign on the score.
# We do this because the score for pairs that we
# exclude need to be subtracted from the score whereas
# scores for pairs that we now can include because of
# that exclude need to be added to the score.
score = -score
# It the pair has already been checked, check its
# next sibling next time around
else:
current[1] += 1
# There are no more nodes to check at this level
else:
# We subtract the cumulative score from the score of the
# pair we are leaving. We do this when we traverse back up
# to the parent or as the last step of each graph finally
# subtracting the total cumulative score from the start node
# score.
score = scores[current[0]] - score
if len(trail):
# Pop the next item on the trail to become our context
# for the next iteration
current = trail.pop()
# Exit criteria... The trail went cold
else:
break
# Add the score to the array
cumulative.append(score)
return cumulative
此方法应返回一个看起来像...的数组
[ 6
, -3
, 3
, 3 ]
5. 只挑选最好的一对
然后我们需要将索引与分数一起存储，以便我们可以在不丢失索引的情况下对分数进行排序。按照我们创建索引列表的顺序对累积分数进行排序indices......
# Sort pairs by score retaining the index to the pair
arr = sorted([(i, cumulative[i])
for i in range(0, len(cumulative))],
key=lambda item: item[1])
看起来像...
[ (1, -3)
, (2, 3)
, (3, 3)
, (0, 6) ]
选择得分最高的项目，同时删除排除的项目，这样我们就保留了最好的配对并丢弃了最差的...
def get_best_pairs(a, b):
pairs = get_pairs(a, b)
excludes = get_pairs_excluded_by_pairs(pairs)
scores = get_pairs_scores(pairs, a)
cumulative = get_cumulative_scores_for_pairs(pairs, excludes, scores)
# Sort pairs by score retaining the index to the pair
arr = sorted([(i, cumulative[i])
for i in range(0, len(cumulative))],
key=lambda item: item[1])
# Work through in order of scores to find the best pair combination
top = []
while len(arr):
topitem = arr.pop()
top.append(topitem[0])
# Remove the indices that are excluded by this one
arr = [(i, score)
for i, score in arr
if i not in excludes[topitem[0]]]
# Sort the resulting pairs by index
return sorted([pairs[i] for i in top], key=lambda item: item[0])
我们的top列表看起来像，其中带有索引的对1已被删除，因为它得分低并被得分较高的对排除在外......
[ (0, 0)
, (1, 2)
, (2, 3) ]
6. 构建结果
对选定的对进行排序，并通过将每个索引递增到下一对来构建结果。当我们用完对增量直到我们到达每个列表的末尾......
def get_indexes_for_best_pairing(a, b):
pairs = get_best_pairs(a, b)
result = [];
i = 0
j = 0
next = None
pair = None
while True:
# This is the first loop or we just dropped a pair into the result
# vector so we need to get the next one
if next == None:
# Get the next pair and we will increment the index up to this
if len(pairs):
next = pairs.pop(0)
pair = next
# No more pairs increment the index to the end of both lists
else:
next = (len(a), len(b))
pair = None
# We increment the index of the first list first
if i < next[0]:
result.append((i, None))
i += 1
# We increment the index of the second list when first has reached
# the next pair
elif j < next[1]:
result.append((None, j))
j += 1
# If both indexes are fully incremented up to the next pair and we
# have a pair to add we add it to the result and increment both
# clearing the next parameter so we get a new one next time around
elif pair != None:
result.append((pair[0], pair[1]));
i += 1
j += 1
next = None
# We reached the end
else:
break
return result
最后我们的结果看起来像......
[ (0, 0)
, (None, 1)
, (1, 2)
, (2, 3)
, (3, None) ]