Obtenga eficientemente sumas ordenadas de una lista ordenada

StackOverflow https://stackoverflow.com/questions/826

  •  08-06-2019
  •  | 
  •  

Pregunta

Tienes una lista ascendente de números, cuál es el algoritmo más eficiente que se te ocurre para obtener la lista ascendente de sumas de cada dos números de esa lista.Los duplicados en la lista resultante son irrelevantes; puedes eliminarlos o evitarlos si lo deseas.

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

¿Fue útil?

Solución

Editar a partir de 2018:Probablemente deberías dejar de leer esto.(Pero no puedo eliminarlo porque está aceptado).

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

Notarás que dado que M[i,j] <= M[i,j+1] y M[i,j] <= M[i+1,j], entonces solo necesitas examinar la parte superior izquierda " esquinas" y elija la más baja.

p.ej.

  • solo 1 esquina superior izquierda, elige 2
  • solo 1, elige 5
  • 6 u 8, elige 6
  • 7 u 8, elige 7
  • 9 u 8, elige 8
  • 9 o 9, elige ambos :)
  • 10 o 10 o 10, elige todo
  • 12 u 11, elige 11
  • 12 o 12, elige ambos
  • 13 o 13, elige ambos
  • 14 o 14, elige ambos
  • 15 o 16, elige 15
  • solo 1, elige 16
  • solo 1, elige 17
  • solo 1, elige 18

Por supuesto, cuando tienes lotes de las esquinas superiores izquierdas, entonces esta solución se transfiere.

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

Otros consejos

En lugar de codificar esto, pienso pseudocodificarlo en pasos y explicar mi lógica, para que los mejores programadores puedan encontrar 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 sumando un número a sí mismo.Al final, tenemos una lista de aproximadamente 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, debido a que las listas se ordenaron por diseño (agregue un número a cada elemento en una lista ordenada y la lista aún estará ordenada), podemos simplemente hacer una ordenación por combinación fusionando cada lista en lugar de ordenar por fusión todo el lote.Al final, esto debería llevar 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 combinación sería entonces el paso de combinación normal con una verificación para asegurarse de que no haya sumas duplicadas.No escribiré esto porque cualquiera puede buscar mergesort.

Entonces ahí está mi solución.Todo el algoritmo es tiempo O (n ^ 2).No dude en señalar cualquier error o mejora.

Puedes hacer esto en dos líneas en Python con

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

El costo de esto es n^2 (¿tal vez un factor logarítmico 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].Entonces, si desea generar esta lista, 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 de Frederickson y Johnson (ver aquí para detalles sangrientos).Aunque esto probablemente pueda modificarse para generarlos en línea reutilizando la computación y obtener un generador eficiente para este conjunto.

@deuseldorf, Peter hay cierta confusión sobre (¡n!) Dudo seriamente que Deuseldorf significara "n factorial" pero simplemente "n, (muy emocionado)!"

Lo mejor que se me ocurrió es producir una matriz de sumas de cada par y luego fusionar las filas, al estilo de fusión.Siento que me falta una idea 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)

Encontré una mejora menor, una que se adapta mejor a la codificación diferida basada en flujos.En lugar de fusionar las columnas por pares, combínelas todas a la vez.La ventaja es que empiezas a obtener elementos de la lista inmediatamente.

-- 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 sabes que vas a utilizar todas las sumas y no hay ninguna ventaja en obtener algunas de ellas antes, elige 'foldl merge []', ya que es más rápido.

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

No importa lo que haga, sin restricciones adicionales en los valores de entrada, no puede hacerlo mejor que O(n^2), simplemente porque tiene que recorrer 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).

Esta pregunta ha estado destrozando mi cerebro durante aproximadamente un día.Impresionante.

De todos modos, no puedes alejarte fácilmente de la naturaleza n^2, pero puedes hacerlo un poco mejor con la combinación, ya que puedes limitar el rango para insertar cada elemento.

Si miras todas las listas que generas, tienen la siguiente forma:

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

Si lo giras 90 grados, obtienes:

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

Ahora, el proceso de fusión debería tomar dos listas. i y i+1 (que corresponden a listas donde el primer miembro es siempre a[i] y a[i+1]), puede limitar el rango para insertar el elemento (a[i + 1], a[j]) en la lista i por la ubicación de (a[i], a[j]) y la ubicación de (a[i + 1], a[j + 1]).

Esto significa que debes fusionar a la inversa en términos de j.No sé (todavía) si puedes aprovechar esto en todos j también, pero parece posible.

Si está buscando una solución verdaderamente independiente del lenguaje, en mi opinión, se sentirá muy decepcionado porque se quedará atrapado con un bucle for y algunos condicionales.Sin embargo, si lo abrió a lenguajes funcionales o características de lenguaje funcional (lo estoy mirando LINQ), mis colegas aquí pueden llenar esta página con ejemplos elegantes en Ruby, Lisp, Erlang y otros.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top