Efficiente ordinati somme di un elenco ordinato

08-06-2019
|

Domanda

Si dispone di un crescente elenco di numeri, che è il più efficiente algoritmo si può pensare di ottenere la crescente lista di somme di ogni due numeri in quella lista.Duplicati nella lista sono irrilevanti, è possibile rimuovere o evitare se si come.

Per essere chiari, non mi interessa l'algoritmo.Sentitevi liberi di postare il codice in qualsiasi linguaggio e paradigma che ti piace.

Soluzione

La modifica del 2018:Probabilmente si dovrebbe smettere di leggere questo.(Ma non riesco a eliminarlo come sarà accettata.)

Se si scrive la somma di simile a questo:

1 4  5  6  8  9
---------------
2 5  6  7  9 10
  8  9 10 12 13
    10 11 13 14
       12 14 15
          16 17
             18

Si noterà che, poiché M[i,j] <= M[i,j+1] e M[i,j] <= M[i+1,j], allora avete solo bisogno di esaminare in alto a sinistra "angoli" e scegliere il più basso.

ad es.

solo 1 angolo in alto a sinistra, scegli 2
solo 1, pick 5
6 o 8, pick 6
7 o 8, pick 7
9 o 8, pick 8
9 o 9, prendere entrambi :)
10 o 10 o 10, di raccogliere tutti
12 o 11, pick 11
12 o 12, prendere entrambi
13 o 13, prendere entrambi
14 o 14, prendere entrambi
15 o 16, scegli 15
solo 1, pick 16
solo 1, pick 17
solo 1, pick 18

Naturalmente, quando si hanno un sacco in alto a sinistra angoli allora questa soluzione incombe.

Sono abbastanza sicuro che questo problema è Ω(n2), perché bisogna calcolare le somme per ogni M[i,j] -- a meno che qualcuno abbia un miglior algoritmo per la somma :)

Altri suggerimenti

Piuttosto che codifica questo, immagino che sarò in pseudo-codice in passaggi e spiegare la mia logica, quindi meglio che i programmatori possono colpire i fori nella mia logica, se necessario.

Il primo passo inizia con un elenco di numeri di lunghezza n.Per ogni numero, abbiamo bisogno di creare una lista di lunghezza n-1, perché non siamo aggiunta di un numero per se stesso.Alla fine abbiamo una lista di circa n gli elenchi ordinati che è stato generato in O(n^2).

step 1 (startinglist) 
for each number num1 in startinglist
   for each number num2 in startinglist
      add num1 plus num2 into templist
   add templist to sumlist
return sumlist

Nel passaggio 2, perché le liste sono stati ordinati per la progettazione (aggiungere un numero per ogni elemento in una lista ordinata e l'elenco sarà ancora ordinati), si può semplicemente fare un mergesort dalla fusione di ciascuna lista insieme, piuttosto che mergesorting l'intero lotto.Alla fine questo dovrebbe avvenire in un tempo O(n^2).

step 2 (sumlist) 
create an empty list mergedlist
for each list templist in sumlist
   set mergelist equal to: merge(mergedlist,templist)
return mergedlist

Il metodo merge sarebbe quindi la normale fusione passo con un controllo per verificare che non ci siano duplicati somme.Non voglio scrivere questo perché chiunque può cercare mergesort.

Quindi c'è la mia soluzione.L'intero algoritmo è O(n^2).Sentitevi liberi di segnalare eventuali errori o miglioramenti.

Si può fare questo in due righe in python con

allSums = set(a+b for a in X for b in X)
allSums = sorted(allSums)

Il costo di questo è n^2 (forse un extra di registro fattore per il set?) per l'iterazione e la s * log(s) per lo smistamento, dove s è la dimensione dell'insieme.

La dimensione del set potrebbe essere grande come n*(n-1)/2 per esempio, se X = [1,2,4,...,2^n].Quindi, se si desidera generare questo elenco ci vorranno almeno n^2/2 nel peggiore dei casi, poiché questa è la dimensione dell'output.

Tuttavia, se si desidera selezionare i primi k elementi di un risultato che si può fare questo in O(kn) utilizzando un algoritmo di selezione per la ordinati X+Y matrici Frederickson e Johnson (vedi qui per dettagli scabrosi).Anche se questo può forse essere modificato per generare on-line attraverso il riutilizzo di calcolo e di ottenere un efficiente generatore per questa serie.

@deuseldorf, Pietro C'è una certa confusione circa (n!) Dubito seriamente deuseldorf il significato di "n fattoriale", ma semplicemente "n, (molto eccitato)!"

Il meglio che ho potuto venire con è quello di produrre una matrice di somme di ogni coppia, e poi unire le righe insieme, a-la merge sort.Sento che mi manca qualche semplice intuizione che si rivelerà molto più efficiente soluzione.

Il mio algoritmo, in Haskell:

matrixOfSums list = [[a+b | b <- list, b >= a] | a <- list]

sortedSums = foldl merge [] matrixOfSums

--A normal merge, save that we remove duplicates
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = case compare x y of
    LT -> x:(merge xs (y:ys))
    EQ -> x:(merge xs (dropWhile (==x) ys))
    GT -> y:(merge (x:xs) ys)

Ho trovato un miglioramento minore, che è più suscettibile per i più pigri, basata sul flusso di codifica.Invece di unire le colonne pair-wise, unire tutti in una volta.Il vantaggio è che si inizia a ottenere elementi della lista immediatamente.

-- wide-merge does a standard merge (ala merge-sort) across an arbitrary number of lists
-- wideNubMerge does this while eliminating duplicates
wideNubMerge :: Ord a => [[a]] -> [a]
wideNubMerge ls = wideNubMerge1 $ filter (/= []) ls
wideNubMerge1 [] = []
wideNubMerge1 ls = mini:(wideNubMerge rest)
    where mini = minimum $ map head ls
          rest = map (dropWhile (== mini)) ls

betterSortedSums = wideNubMerge matrixOfSums

Tuttavia, se sai che stai andando a utilizzare tutte le somme, e non c'è nessun vantaggio per ottenere alcuni dei loro precedenti, andare con 'foldl merge []', in quanto è più veloce.

In SQL:

create table numbers(n int not null)
insert into numbers(n) values(1),(1), (2), (2), (3), (4)


select distinct num1.n+num2.n sum2n
from numbers num1
inner join numbers num2 
    on num1.n<>num2.n
order by sum2n

C# LINQ:

List<int> num = new List<int>{ 1, 1, 2, 2, 3, 4};
var uNum = num.Distinct().ToList();
var sums=(from num1 in uNum
        from num2 in uNum 
        where num1!=num2
        select num1+num2).Distinct();
foreach (var s in sums)
{
    Console.WriteLine(s);
}

Non importa quello che fai, senza ulteriori vincoli sui valori di input, si può fare meglio di O(n^2), semplicemente perché è necessario scorrere tutte le coppie di numeri.L'iterazione dominare ordinamento (che si può fare in un tempo O(n log n) o più veloce).

Questa domanda è stata wracking il mio cervello per circa un giorno.Impressionante.

Comunque, non puoi scappare da n^2 natura di facilmente, ma si può fare leggermente meglio con l'unione in quanto si limita la gamma di inserire ogni elemento.

Se si guarda a tutte le liste che si genera, hanno la seguente forma:

(a[i], a[j]) | j>=i

Se girate di 90 gradi, si ottiene:

(a[i], a[j]) | i<=j

Ora, il processo di unione dovrebbe essere l'assunzione di due liste i e i+1 (che corrispondono alle liste di cui il primo membro è sempre a[i] e a[i+1]), si limita la gamma di inserire elemento (a[i + 1], a[j]) in lista i dalla posizione di (a[i], a[j]) e la posizione di (a[i + 1], a[j + 1]).

Questo significa che si deve unire in senso inverso in termini di j.Non so (ancora) se è possibile sfruttare questo fronte j come pure, ma sembra possibile.

Se siete alla ricerca di un veramente indipendente dalla lingua soluzione allora si sarà molto deluso, a mio parere, perché ti verrà bloccato con un ciclo for, e alcune istruzioni condizionali.Tuttavia, se si apre a linguaggi funzionali o funzionali caratteristiche del linguaggio (sto guardando te LINQ) quindi i miei colleghi qui in grado di riempire questa pagina con eleganti esempi di Rubino, Lisp, Erlang, e altri.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow