我有以下两个有序的项目列表：
A = ["apples","oranges","bananas","blueberries"]
B = ["apples","blueberries","oranges","bananas"]
每个项目的分数等于字符串的长度，所以......
apples = 6 points
oranges = 7 points
bananas = 7 points
blueberries = 11 points
我想创建一个对（A，B）列表，其中包含A的索引或B的索引或两者的索引，而不更改它们在每个列表中出现的顺序。
然后每一对都有其项目的分数，因此通过配对项目，我们将两个项目的总分减半。我想获得分数最小的对的组合。
例如，在上面的两个列表中，每个项目都可以配对，但有些配对会阻止我们配对其他配对，因为我们无法在不更改其中一个列表的顺序的情况下将两者配对。例如，我们不能将"blueberries"和"oranges"配对，因为"oranges"在"blueberries"之前出现在一个列表中，但在另一个列表之后。我们只能配对一个或另一个。每个列表也可以多次具有相同的项目。
上述问题的最佳结果是......
+---+---+----------------+-------+
| A | B | Value | Score |
+---+---+---+----------------+-------+
| 0 | 0 | 0 | "apples" | 6 |
+---+---+---+----------------+-------+
| 1 | - | 1 | "blueberries" | 11 |
+---+---+---+----------------+-------+
| 2 | 1 | 2 | "oranges" | 7 |
+---+---+---+----------------+-------+
| 3 | 2 | 3 | "bananas" | 7 |
+---+---+---+----------------+-------+
| 4 | 3 | - | "blueberries" | 11 |
+---+---+---+--------+-------+-------+
| Total | 42 |
+-------+-------+
我认为答案是这样的：
通过将对从一个列表连接到另一个列表，我可以确定哪些对在视觉上排除了哪些对，如果该连接与另一个连接相交，则它将其排除。我不确定如何以编程方式完成此操作。
我怎么解决这个问题？
请注意，我的回答假设只有2个列表，并且每个列表中的项目最多只能有一次。
您要做的第一件事是构建一个地图/字典，其中项目作为键，一对整数作为值。此映射将包含两个数组中一个项的索引。运行第一个列表并将索引放在该对的第一个值中，并将第二个值放在-1中。对第二个列表执行相同操作但显然将索引放在第二个值中。像这样的东西：
pairs = map<string, pair<int, int>>
i = 0
while i < A.Length
pairs[A[i]].first = i
pairs[A[i]].second = -1
i++
i = 0
while i < B.Length
pairs[B[i]].second = i
i++
现在，您必须确定可以执行的对组合。此伪代码创建所有可能组合的列表：
i = 0
while i < A.Length
j = i
index = -1
combination = list<pair>
while j < A.Length
pair = pairs[A[j]]
if pair.second > index
combination.add(pair)
index = pair.second
j++
combinations.add(combination)
i++
现在，剩下的就是权衡可能的组合，但不要忘记包括未配对的项目。
编辑
我现在想的是为每个项目构建一个所有可能对的映射。会产生以下结果的东西。
oranges: [0,2][0,5][5,2][5,5][0,-1][-1,2][5,-1][-1,5]
apples: [1,1][1,-1][-1,1]
bananas: [2,3][2,-1][-1,3]
...
使用排除逻辑，我们可以对这些对进行分组，并生成对列表列表的映射。
oranges: [0,2][5,-1][-1,5], [0,5][5,-1][-1,2], ..., [0,-1][5,-1][-1,2][-1,5]
apples: [1,1], [1,-1][-1,1]
...
现在，每个项目只能在结果输出中使用一个对的列表，而某些列表在不同的项目之间相互排斥。剩下的就是提出一种算法来权衡每种可能性。
我已将问题分解为子问题...检查它的测试是否按预期工作：
# 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!")
使用相关索引列表创建列表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) ]
只需循环遍历对并查找原始列表中的值：
def get_pairs_scores(pairs, a):
return [len(a[i]) for i, _ in pairs]
对于每一对找到它排除的其他对...
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] ]
加上被排除在外的对的分数......等等等等。
使用深度优先算法遍历排除的非循环图以获得每对的累积分数......这是我们需要做的事情......
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 ]
然后我们需要使用分数存储索引，以便我们可以在不丢失索引的情况下对分数进行排序。对累积分数进行排序，以便我们创建索引列表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) ]
对所选对进行排序，并通过将每个索引递增到下一对来构建结果。当我们用完对数增量时，直到我们到达每个列表的末尾...
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) ]