Comment trouver pair avec KTH plus grande somme?

EDIT: cela ne fonctionne pas. je laisse la réponse, puisque apparemment je ne suis pas le seul à avoir ce genre d'idée; voir la discussion ci-dessous. Un contre-exemple est x = (2, 3, 6), y = (1, 4, 5) et k=3, où l'algorithme donne 7 (3+4) au lieu de 8 (3+5).

Let x et y les deux tableaux, triés par ordre décroissant; nous voulons construire l' K-ième somme la plus importante.

Les variables sont: i la index dans le premier tableau (élément x[i]),j l'index dans le deuxième tableau (élément y[j]) et k la "commande" de la somme (k1..K), dans le sens que S(k)=x[i]+y[j] sera le k - e plus grande somme satisfaisant vos conditions (c'est l'invariant de boucle).

Démarrer (i, j) égal (0, 0):S(1) = x[0]+y[0].

k1K-1:

• si x[i+1]+ y[j] > x[i] + y[j+1], puis i := i+1 (et j ne change pas) ; sinon j:=j+1

Pour voir que cela fonctionne, vous avez S(k) = x[i] + y[j]. Alors, S(k+1) est la plus grande somme qui est inférieure (ou égale) à S(k), et comme au moins un élément (i ou j) des changements. Il n'est pas difficile de voir que justement l'un des i ou j devrait changer. Si i change, la plus grande somme que vous pouvez construire qui est inférieure à S(k) en mettant i=i+1, parce que x est en baisse et tous les x[i'] + y[j]i' < i sont plus grands que S(k). La même chose vaut pour j, montrant que S(k+1)x[i+1] + y[j] ou x[i] + y[j+1].

par conséquent, à la fin de la boucle vous avez trouvé le K-ième plus grande somme.

tl; dr: si vous regardez devant et regardez derrière à chaque itération, vous pouvez commencer par la fin (qui est la plus haute) et travailler en O(K) fuseau.

bien que la perspicacité qui sous-tend cette approche soit, je crois, saine, le code ci-dessous n'est pas tout à fait correct à l'heure actuelle (voir les commentaires).

voyons voir: tout d'abord, les tableaux sont triés. Donc, si les tableaux sont a et b longueur M et N, et comme vous les avez arrangés, plus les éléments sont dans les logements M et N respectivement, la plus grosse paire sera toujours a[M]+b[N].

maintenant, quelle est la deuxième plus grande paire? Il va peut-être l'un des {a[M],b[N]} (il ne peut pas avoir les deux, parce que c'est juste la plus grande paire de nouveau), et au moins un de {a[M-1],b[N-1]}. MAIS, nous savons aussi que si nous choisissons a[M-1]+b[N-1], nous pouvons faire un des opérandes plus grand en choisissant le nombre plus élevé de la même Liste, donc il aura exactement un nombre de la dernière colonne, et l'une à partir de l'avant-dernière colonne.

Considérer les deux tableaux: a = [1, 2, 53]; b = [66, 67, 68]. Notre plus haute paire est 53+68. Si nous perdons le plus petit de ces deux, notre paire est 68+2; si nous perdons le plus, c'est 53+67. Nous devons donc nous tourner vers l'avenir pour décider de ce que sera notre prochaine paire. La stratégie la plus simple consiste simplement à calculer la somme des deux paires possibles. Cela coûtera toujours deux additions, et deux comparaisons pour chaque transition (trois parce que nous devons traiter avec cas où les sommes sont égales);appelons de coût Q).

au début, j'ai été tenté de répéter que K-1 fois. Mais il y a un problème: la paire la plus grosse suivante pourrait bien être l'autre paire que nous pouvons valablement faire à partir de {{a[M],b[N]}, {a[M-1],b[N-1]}. Donc, nous devons aussi regarder derrière nous.

Alors, allons-code (python, doit être de 2/3 compatible):

def kth(a,b,k):
    M = len(a)
    N = len(b)
    if k > M*N:
       raise ValueError("There are only %s possible pairs; you asked for the %sth largest, which is impossible" % M*N,k)
    (ia,ib) = M-1,N-1 #0 based arrays
    # we need this for lookback
    nottakenindices = (0,0) # could be any value
    nottakensum = float('-inf')
    for i in range(k-1):
        optionone = a[ia]+b[ib-1]
        optiontwo = a[ia-1]+b[ib]
        biggest = max((optionone,optiontwo))
        #first deal with look behind
        if nottakensum > biggest:
           if optionone == biggest:
               newnottakenindices = (ia,ib-1)
           else: newnottakenindices = (ia-1,ib)
           ia,ib = nottakenindices
           nottakensum = biggest
           nottakenindices = newnottakenindices
        #deal with case where indices hit 0
        elif ia <= 0 and ib <= 0:
             ia = ib = 0
        elif ia <= 0:
            ib-=1
            ia = 0
            nottakensum = float('-inf')
        elif ib <= 0:
            ia-=1
            ib = 0
            nottakensum = float('-inf')
        #lookahead cases
        elif optionone > optiontwo: 
           #then choose the first option as our next pair
           nottakensum,nottakenindices = optiontwo,(ia-1,ib)
           ib-=1
        elif optionone < optiontwo: # choose the second
           nottakensum,nottakenindices = optionone,(ia,ib-1)
           ia-=1
        #next two cases apply if options are equal
        elif a[ia] > b[ib]:# drop the smallest
           nottakensum,nottakenindices = optiontwo,(ia-1,ib)
           ib-=1
        else: # might be equal or not - we can choose arbitrarily if equal
           nottakensum,nottakenindices = optionone,(ia,ib-1)
           ia-=1
        #+2 - one for zero-based, one for skipping the 1st largest 
        data = (i+2,a[ia],b[ib],a[ia]+b[ib],ia,ib)
        narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data
        print (narrative) #this will work in both versions of python
        if ia <= 0 and ib <= 0:
           raise ValueError("Both arrays exhausted before Kth (%sth) pair reached"%data[0])
    return data, narrative

Pour les personnes sans python, voici un ideone: http://ideone.com/tfm2MA

Au pire, nous ont 5 comparaisons dans chaque itération, et les itérations K-1, ce qui signifie qu'il s'agit d'un algorithme O(K).

maintenant, il est peut-être possible d'exploiter l'information sur les différences entre les valeurs pour optimiser un peu cela, mais cela permet d'atteindre l'objectif.

Voici une implémentation de référence (pas O(K), mais fonctionnera toujours, à moins qu'il y ait un cas de coin avec des cas où les paires ont des sommes égales):

import itertools
def refkth(a,b,k):
    (rightia,righta),(rightib,rightb) = sorted(itertools.product(enumerate(a),enumerate(b)), key=lamba((ia,ea),(ib,eb):ea+eb)[k-1]
    data = k,righta,rightb,righta+rightb,rightia,rightib
    narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data
    print (narrative) #this will work in both versions of python
    return data, narrative

cela calcule le produit cartésien des deux tableaux (c.-à-d. toutes les paires possibles), les trie par Somme, et prend l'élément kth. enumerate fonction décore chaque article avec son index.

l'algorithme de max-heap dans l'autre question est simple, rapide et correct. Ne pas le frapper. C'est vraiment bien expliqué. https://stackoverflow.com/a/5212618/284795

peut-être qu'il n'y a pas d'algorithme O(k). C'est bon, O(k log k) est presque aussi rapide.

Si les deux dernières solutions sont à (a1, b1), (a2, b2), alors il me semble qu'il existe seulement quatre candidats des solutions de (a1-1, b1) (a1, b1-1) (a2-1, b2) (a2, b2-1). Cette intuition pourrait être erronée. Il y a sûrement au plus quatre candidats pour chaque coordonnée, et le plus haut est parmi les 16 paires (a dans {a1, a2, a1-1, a2-1}, b dans {b1,b2,b1-1, b2-1}). C'est O(k).

(non, ce n'est pas, toujours pas sûr si c'est possible.)

[2, 3, 5, 8, 13]
[4, 8, 12, 16]

fusionner les 2 Tableaux et noter les index dans le tableau trié. Voici le tableau d'index ressemble à (à partir de 1 pas 0)

[1, 2, 4, 6, 8] [3, 5, 7, 9]

maintenant, commencez par la fin et faites des tuples. faites la somme des éléments du tuple et choisissez le kème plus grand total.