重新排列数组 A，以便在进行一对一比较时，A 赢得与数组 B 的最大比较次数

Question

假设我有一个数组 A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1] 和 B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]

重新排列数组 A 的元素，这样当我们按元素比较 3 与 2 和 6 与 7 等等时，我们有最大的胜利（A[i] > B[i] 最大的组合 (0<=i<len(A)) ).

我尝试了以下方法：

def optimal_reorder(A,B,N):
    tagged_A = [('d',i) for i in A]
    tagged_B = [('a',i) for i in B]
    merged = tagged_A + tagged_B
    merged = sorted(merged,key=lambda x: x[1])
    max_wins = 0
    for i in range(len(merged)-1):
        print (i)
        if set((merged[i][0],merged[i+1][0])) == {'a','d'}:
            if (merged[i][0] == 'a') and (merged[i+1][0] == 'd'):
                if (merged[i][1] < merged[i+1][1]):
                    print (merged[i][1],merged[i+1][1])
                    max_wins += 1
    return max_wins

引用自
但是这种方法似乎没有给出给定 A 和 B 的正确答案，即如果 A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1] 和 B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6] 那么最大获胜数是 7，但我的算法给出了 5.

这里有什么我遗漏的吗？

按照@chqrlie

的建议修改了解决方案

def optimal_reorder2(A,B):
    arrA = A.copy()
    C = [None] * len(B)
    for i in range(len(B)):
        k = i + 1
        all_ele = []
        while (k < len(arrA)):
            if arrA[k] > B[i]:
                all_ele.append(arrA[k])
            k += 1
        if all_ele:
            e = min(all_ele)
        else:
            e = min(arrA)
        C[i] = e
        arrA.remove(e)
    return C

Answer 1

这个算法怎么样：

从空数组开始 C。
对于 range(len(B)) 中的每个索引 i。
- 如果A的剩余元素至少有一个大于B[i]，则选择e作为这些元素中最小的，否则选择e作为A.
- 设置 C[i] = e 并从 A 中删除 e。

C 应该是 A 的重新排序，以最大化真实比较的数量 C[i] > B[i].

Answer 2

可能有比这更好的算法，但您可以将其视为最大二分匹配问题。将数组视为二分图中的两组节点，然后如果 A[i] > B[j]，则添加一条从 A[i] 到 B[j] 的边。然后，任何匹配都会告诉您如何将 A 的元素与 B 的元素配对，以便 A 元素“胜过”B 元素，而最大匹配会告诉您如何执行此操作以最大化获胜次数。

我相信有更好的方法可以做到这一点，我很高兴看到其他人想出了什么办法。但这至少表明你可以在多项式时间内解决这个问题。

重新排列数组 A，以便在进行一对一比较时，A 赢得与数组 B 的最大比较次数

Rearrange an array A so that A wins maximum number of comparisons with array B when comparison is done one-on-one

arrays

sorting

mergesort

python-3.x

array-algorithms