Obtenga sumas ordenadas de una lista ordenada

Question

Tiene una lista ascendente de números, ¿cuál es el algoritmo más eficiente que se le ocurre para obtener la lista ascendente de las sumas de cada dos números en esa lista? Los duplicados en la lista resultante son irrelevantes, puede eliminarlos o evitarlos si lo desea.

Para ser claro, estoy interesado en el algoritmo. Siéntase libre de publicar el código en cualquier idioma y paradigma que desee.

Answer 1

Editar a partir de 2018: Probablemente deberías dejar de leer esto. (Pero no puedo borrarlo, ya que se acepta.)

Si se escribe a cabo las sumas así:

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 

Se dará cuenta de que, dado que M [i, j] = < M [ i, j + 1] y M [i, j] < = M [i + 1, j], entonces solo necesita examinar las "esquinas" superiores izquierdas y elegir la más baja.

p. Ej.

• solamente 1 esquina superior izquierda, Seleccionar 2
• solamente 1, coge 5
• 6 o 8, recoger 6
• 7 o 8, recoger 7
• 9 o 8, recoger 8
• 9 o 9, recoger tanto :)
• 10 o 10 o 10, recoger todos
• 12 o 11, recoger 11
• 12 o 12, designe tanto
• 13 o 13, designe tanto
• 14 o 14, designe tanto
• 15 o 16, recoger 15
• solamente 1, coge 16
• solamente 1, recoger 17
• sólo el 1, recoger 18

Por supuesto, cuando se tiene una gran cantidad de las esquinas superiores izquierda y luego esta solución recae.

estoy bastante seguro de que este problema es Ω (N ²), porque hay que calcular las sumas para cada M [i, j] - a menos que alguien tiene un mejor algoritmo para la suma :)

Answer 2

Si está buscando una solución verdaderamente independiente del idioma, se sentirá muy decepcionado con mi opinión, ya que tendrá problemas con un bucle for y algunos condicionales. Sin embargo, si lo abres a idiomas funcionales o funciones de lenguaje funcional (te estoy viendo LINQ), mis colegas aquí pueden llenar esta página con ejemplos elegantes en Ruby, Lisp, Erlang y otros.

Answer 3

Lo mejor que se me ocurre es producir una matriz de sumas de cada par, y luego unir las filas, a-la merge sort. Siento que me falta algo de información simple que revelará una solución mucho más eficiente.

Mi algoritmo, en 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) 

he encontrado una mejora menor, una que sea más susceptible a la codificación basada en secuencias perezoso. En lugar de fusionar las columnas en pares, combine todas a la vez. La ventaja es que comienzas a obtener elementos de la lista de inmediato.

-- 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 

Sin embargo, si usted sabe que va a utilizar todas las sumas, y no hay ventaja para conseguir algunos de ellos antes, ir con 'foldl merge []', ya que es más rápido.

Answer 4

En lugar de codificar esto, creo que voy a pseudocodificarlo en pasos y explicar mi lógica, para que los mejores programadores puedan abrir agujeros en mi lógica si es necesario.

En el primer paso comenzamos con una lista de números de longitud n. Para cada número necesitamos crear una lista de longitud n-1 porque no estamos agregando un número a sí mismo. Al final tenemos una lista de n listas ordenadas que se generó en O (n^2) tiempo.

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 

En el paso 2, ya que las listas fueron ordenados por el diseño (añadir un número a cada elemento de una lista ordenada y la lista seguirá siendo ordenadas) que puede hacer un simple mergesort mediante la fusión de cada lista juntos en lugar de mergesorting todo el lote. Al final, esto debería tomar O (n^2) tiempo.

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

El método de fusión sería entonces la etapa de mezcla normal con una comprobación para asegurarse de que no hay sumas duplicados. No escribiré esto porque cualquiera puede buscar mergesort.

Así que ahí está mi solución. El algoritmo completo es O (n^2) tiempo. Siéntase libre de señalar cualquier error o mejora.

Answer 5

En 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); 
} 

Answer 6

Puede hacerlo de dos líneas en Python con

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

El costo de este es n^2 (tal vez un factor de registro adicional para el conjunto?) para la iteración y s * log (s) para la clasificación donde s es el tamaño del conjunto.

El tamaño del conjunto podría ser tan grande como n * (n-1)/2, por ejemplo, si X = [1,2,4, ..., 2^n]. Por lo tanto, si desea generar esta lista, se necesitará al menos n^2/2 en el peor de los casos, ya que este es el tamaño de la salida.

Sin embargo, si desea seleccionar los primeros k elementos del resultado puede hacerlo en O (kn) usando un algoritmo de selección para matrices X + Y ordenadas por Frederickson y Johnson (see here for gory details). Aunque esto probablemente se puede modificar a generarlos en línea reutilizando el cálculo y obtener un generador eficiente para este conjunto.

@deuseldorf, Peter Existe cierta confusión acerca de (n!) Tengo serias dudas de que deuseldorf signifique "n factorial" sino simplemente "n, (muy emocionado)! "

Answer 7

Esta pregunta ha estado atormentando mi cerebro durante casi un día. Impresionante.

De todas formas, no puede alejarse de la n^2 la naturaleza de él fácilmente, pero se puede hacer un poco mejor con la fusión ya que se puede delimitar el rango de insertar cada elemento.

Si nos fijamos en todo las listas que generan, tienen la siguiente forma:

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

Si le da la vuelta 90 grados, se obtiene:

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

Ahora, t que se funden proceso debe tomar dos listas i y i+1 (que corresponden a las listas donde el primer miembro es siempre a[i] y a[i+1]), se puede delimitar el rango de insertar el elemento (a[i + 1], a[j]) en la lista de i por la ubicación de (a[i], a[j]) y la ubicación de (a[i + 1], a[j + 1]).

Esto significa que debe fusionarse en reversa en términos de j. No sé (todavía) si puede aprovechar esto en j también, pero parece posible.

Answer 8

n importa lo que hagas, sin restricciones adicionales sobre los valores de entrada, no se puede hacer nada mejor que O (n^2), simplemente porque hay que iterar a través de todos los pares de números. La iteración dominará la clasificación (que puede hacer en O (n log n) o más rápido).