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

Question

Let's say I have an array A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1] and B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6]

Rearrange elements of array A so that when we do comparison element-wise like 3 with 2 and 6 with 7 and so on, we have maximum wins (combinations where A[i] > B[i] are maximum (0<=i<len(A))).

I tried below approach:

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

as referenced from
here but this approach doesn't seem to give correct answer for given A and B i,e if A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1] and B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6] then maximum wins is 7 but my algorithm is giving 5.

is there something I am missing here.

revised solution as suggested by @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

score 0 · Accepted Answer · answered May 04 '20 at 18:01

0

How about this algorithm:

start with an empty array C.
for each index i in range(len(B)).
- if at least one of the remaining elements of A is larger than B[i], choose e as the smallest of these elements, otherwise choose e as the smallest element of A.
- set C[i] = e and remove e from A.

C should be a reordering of A that maximises the number of true comparisons C[i] > B[i].

answered May 04 '20 at 18:01

chqrlie

131,814
10
121
189

Implemented your algorithm and it seems to give correct answer now for test case specified above and also in https://stackoverflow.com/questions/35806804/rearrange-an-array-to-be-optimal-in-comparison-to-another-array. However wondering if this is the generic solution that solves extreme test cases where there is repetition allowed in both arrays – Vikas Chitturi May 05 '20 at 05:27
I edited the question with revised solution as per your suggestion @chqrlie – Vikas Chitturi May 05 '20 at 05:35
@VikasChitturi: I did not find a formal proof that this algorithm finds a good solution in all cases, nor did I find a counter example. It seems repeated entries should not make a difference, but again I cannot prove it. – chqrlie May 05 '20 at 12:12

score 0 · Answer 2 · answered May 05 '20 at 05:39

There’s probably a much better algorithm than this, but you can think of this as a maximum bipartite matching problem. Think of the arrays as the two groups of nodes in the bipartite graph, then add an edge from A[i] to B[j] if A[i] > B[j]. Then any matching tells you how to pair elements of A with elements of B such that the A element “wins” against the B element, and a maximum matching tells you how to do this to maximize the number of wins.

I’m sure there’s a better way to do this, and I’m excited to see what other folks come up with. But this at least shows you can solve this in polynomial time.

food for thought! thanks. Another solution is to naively take every permutation of array A, do comparisions and count the number of wins, At the end take the max of all the wins counts.(I just coded it using python's itertools but its like exponential time complexity) — Vikas Chitturi, May 05 '20 at 06:12

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

2 Answers2