переставить массив A так, чтобы A выигрывало максимальное количество сравнений с массивом B, когда сравнение выполняется один на один - PullRequest
Новая
       85

переставить массив A так, чтобы A выигрывало максимальное количество сравнений с массивом B, когда сравнение выполняется один на один

1 голос
/ 04 мая 2020

Допустим, у меня есть массив 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 i, e если A = [3, 6, 7, 5, 3, 5, 6, 2, 9, 1] и B = [2, 7, 0, 9, 3, 6, 0, 6, 2, 6], то максимальный выигрыш равен 7, но мой алгоритм дает 5.

есть что-то, чего я здесь упускаю .

пересмотренное решение, предложенное @ chqrl ie

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

Ответы [ 2 ]

0 голосов
/ 05 мая 2020

Вероятно, есть гораздо лучший алгоритм, чем этот, но вы можете думать об этом как о проблеме максимального согласования двухстороннего взаимодействия Думайте о массивах как о двух группах узлов в двудольном графе, затем добавьте ребро от A [i] до B [j], если A [i]> B [j]. Затем любое сопоставление говорит вам, как соединить элементы A с элементами B так, чтобы элемент A «выиграл» против элемента B, а максимальное сопоставление говорит вам, как это сделать, чтобы максимизировать количество побед.

Я уверен, что есть лучший способ сделать это, и я рад видеть, что другие люди придумывают. Но это по крайней мере показывает, что вы можете решить эту проблему за полиномиальное время.

0 голосов
/ 04 мая 2020

Как насчет этого алгоритма:

  • начать с пустого массива C.
  • для каждого индекса i в range(len(B)).
    • , если хотя бы один из оставшихся элементов A больше B[i], выберите e в качестве наименьшего из этих элементов, в противном случае выберите e в качестве наименьшего элемента A.
    • установить C[i] = e и удалить e из A.

C должно быть переупорядочением A, которое максимизирует число истинных сравнений C[i] > B[i].

...