Un algoritmo per trovare una coppia di somme da un elenco di numeri?

Question

Supponiamo di avere il seguente elenco di numeri {3,6,10,9,13,16,19}, non necessariamente in questo ordine. Ora, non sapendo che questo è l'insieme della possibile combinazione del set {3,6,10}, c'è un algoritmo, in qualsiasi linguaggio di programmazione che può essere usato per trovare queste combinazioni in modo efficiente. Fondamentalmente, voglio recuperare l'elenco dal set totale - dove sono inclusi tutti i numeri. Che cos'è un algoritmo efficiente, non desidero reinventare la ruota se ne esiste già una?

Answer 1

Per il caso generale in cui ci può essere un qualsiasi numero di elementi, ecco un O (q * log (q)) algoritmo dove q è la dimensione della lista in ingresso:

1. ordine dell'elenco q in ordine crescente.
2. Rimuovere l'elemento più piccolo, m, e aggiungerlo al set di risultati. Rimuovilo da q.
3. Iterate over q. Mantieni un elenco di numeri che abbiamo visto. Se vediamo un numero che è (un numero che abbiamo già visto + m), allora scartalo. Questo dovrebbe mantenere la metà dei numeri (tutti quelli che non implicano m).
4. Ripetere dal passaggio 2 finché non vengono trovati tutti i numeri.

Ecco un'implementazione di questo algoritmo in Python:

def solve(q): 
    q = sorted(q) 
    x = [] 
    while q: 
     x.append(q[0]) 

     s = [False]*len(q) 
     s[0] = True 
     j = 1 

     for i in range(1, len(q)): 
      if q[i] == q[0] + q[j]: 
       s[i] = True 
       j += 1 
       while j < len(q) and s[j]: 
        j += 1 

     q = [k for k, v in zip(q, s) if not v] 
    return x 

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99] 
from itertools import combinations 
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r)) 
print(solve(q)) 

Risultato:

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99] 

---

risposta originale:

Supponendo che ci sono solo 3 numeri nella elenca e nessun numero può essere negativo:

Due dei numeri devono essere i due numeri più piccoli nell'elenco. Il numero più grande deve essere la somma di tutti e tre. Per sottrazione puoi trovare il terzo numero.

Answer 2

1) Trova i due numeri più piccoli, questi devono far parte della lista originale.

2) Trova la loro somma, tutto più piccolo nell'elenco deve essere parte della lista originale.

3) Trovare la somma più piccola successiva e ripetere fino a quando tutte le somme di due numeri sono state eseguite.

Ogni volta che si aggiunge un numero all'elenco originale o si trova una somma, rimuoverla dalla lista grande.

4) Continuare con 3 numeri di somme e continuare ad aumentare finché la lista grande non è vuota.

Edit:

Trovare la prossima piccola somma richiede un elenco ordinato dei numeri. Se la tua lista è A, B, C, D, E allora la somma più piccola è A + B e la somma più piccola successiva è A + C.

Le prestazioni sono terribili: 2^N, ma se sto leggendo correttamente la tua domanda, l'elenco contiene l'elenco originale e tutte le possibili somme che ti consentono di aumentare considerevolmente le prestazioni.

Ad esempio, sai quanti numeri stai cercando, il che significa che sai quando ne hai bisogno solo uno e poiché anche tu conosci il numero più grande nell'elenco, l'ultimo numero è il numero più grande meno tutti i numeri già aggiunto al tuo elenco originale.

Answer 3

Ecco come lo si fa. O almeno è una soluzione ingenua.

In primo luogo si ordinano i numeri in ordine crescente. Supponendo che A sia l'elenco dei risultati ordinato e S è l'insieme di numeri minimi da cui è possibile costruire A.

Passare attraverso A. Mentre non esiste un sottoinsieme di S che somma fino a un _i aggiungere un nuovo numero a S tale che faccia.

Sulla prima iterazione verrà aggiunto min (A). Il secondo numero sarà probabilmente in S. Questo è abbastanza intenso dal punto di vista computazionale perché per ogni numero esaminato in A è necessario assicurarsi che esista un sottoinsieme di S che lo aggiunge e che non si aggiunga un numero che crea un sottoinsieme di S che aggiunge qualcosa in A.

È possibile ottimizzarlo alquanto, ogni volta che si aggiunge un numero a S, si elaborano tutte le somme possibili compreso quel nuovo elemento e rimuovendole da A. Keep andare fino a vuoto A.

Diventa complicato se i numeri possono essere negativi ma lo vedrai perché ci sarà un elemento negativo di A affinché questo sia possibile.