注意，我的答案假设只有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

地图看起来像。。。

{ "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

对如下所示。。。

[ (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\u 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 ]

然后我们需要存储带有分数的索引，这样我们就可以在不丢失索引的情况下对分数进行排序。按顺序对累积分数进行排序，我们创建索引index的列表...

# 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])

我们的顶部列表看起来是这样的，索引为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) ]