問題をサブの問題に分割しました...それを確認するテストはすべて期待どおりに機能しています:
# 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) ]