algorithm - niños - ordenar 4 numeros forma ascendente c++

Iterando sobre pares de números en orden creciente

Question

Explicaré de dónde viene la pregunta al final, pero aquí está la declaración. Supongamos que tengo dos listas de enteros no negativos, que escribiré (A[0] ... A[n]) y (B[0] ... B[m]) . Están aumentando estrictamente, por lo que A[i+1] > A[i] para todos i y de manera similar para B Quiero recolectar todos los pares de elementos n * m en orden creciente de su suma.

Entonces, por ejemplo, si A = (0 1 2) y B = (1 4) , entonces quiero terminar recolectando ((0 1) (1 1) (2 1) (0 4) (1 4) (2 4)) . Si hay un empate, no me importa en qué orden recojo los dos elementos. Por ejemplo, si A = (0 1) y B = (0 1) , entonces no me importa cuál de los términos mixtos, (0 1) o (1 0) , recojo primero.

Obviamente, me gustaría que esto fuera razonablemente eficiente. Espero que sea posible en tiempo asintótico a m * n . Específicamente, espero que la entrada ordenada haga este problema estrictamente más fácil que el problema equivalente si no supiera nada acerca de las entradas. En lo que estaba pensando cuando hice la pregunta por primera vez fue la cantidad de estado que tenemos que almacenar. Esperaba que fuera posible con una cantidad constante, pero tal vez esto no sea realista. (¡Las cosas que he probado desde entonces han fallado!)

El código realmente se escribirá en Lisp, pero creo que la declaración del problema es bastante independiente de eso. Lo más natural es que las entradas vengan como listas enlazadas individualmente, pero de todos modos tendré que revertirlas por adelantado, de modo que si el acceso aleatorio es relevante, puedo hacer matrices. En caso de que sea relevante, espero que esto se haga en su mayoría en listas bastante pequeñas, por lo que un término constante masivo / factor constante en el tiempo de ejecución probablemente excluya una solución. (¡Aunque me encantaría saber sobre la idea del algoritmo!)

Antecedentes: he estado buscando en el código fuente de Maxima, un sistema de álgebra computacional y, en particular, en su código para la multiplicación de dos polinomios. Los polinomios se representan en un "formato disperso", por lo que x^5 + x^2 + 2 puede aparecer como (5 1 2 1 0 2) , con exponentes descendentes seguidos de sus respectivos coeficientes. Para calcular el producto de manera eficiente, lo que realmente quiero hacer es recopilar los términos de grado cero, luego los términos de grado 1, etc. El código actual evita resolver este problema haciendo una punzada a medias por eficiencia, y luego haciendo una tipo de adición polinomial genérica para tratar los coeficientes en un orden que no espera. ¡Siento que deberíamos poder hacerlo mejor!

Answer 1

Espero que sea posible almacenar solo una cantidad constante de estado y solo iterar sobre cada lista una vez.

Creo que esto es imposible. No puedo proporcionar una prueba matemática rigurosa, pero considere esto: su problema tiene dos partes:

1) Genere todos los pares de A y B. 2) Asegúrese de que estén en orden de suma creciente.

Vamos a soltar la segunda parte para que sea más fácil. La forma más simple posible de implementar esto es

foreach a in A:
  foreach b in B:
    emit (a, b)

Espero que estén de acuerdo en que no puede haber una manera más eficiente de hacer esto. Pero aquí ya iteramos sobre B longitud (A) veces.

Por lo tanto, la complejidad de tiempo mínima para esto es O (A * B), pero desea O (A + B).

Answer 2

Así que tomemos dos ''matices matrices'' sA y sB, que contienen solo cifras de grados / coeficientes no nulos como se describe en la publicación original.
ejemplo:

A   =  x^5 + 3*x^2 + 4
sA  = [ 5, 1, 2, 3, 0, 4 ]

B = 2*x^6 + 5*x^3 + 8*x
sB = [ 6, 2, 3, 5, 1, 8]

Lo que sugiero es hacer la operación de la manera en que lo haríamos a mano, por lo que toman un tiempo en m * n, donde m, n es el número de coeficientes no nulos, y no en p * q, donde p y q son los grados de A, B.
Como dijiste que myn son pequeños, m * n no es gran cosa.
Para almacenar los coeficientes mientras se computa, use una matriz dispersa (puede ser costosa) o una tabla hash. el índice o clave es el grado, mientras que el valor es el coeficiente correspondiente.
Aquí un ejemplo de implementación en javascript, usando una tabla hash:

http://jsbin.com/ITIgokiJ/2/edit?js,console

un ejemplo :

A     =   "x^5+3x^2+4"
B     =   "2x^6+5x^3+8x^1"
A * B =   "2x^11+11x^8+16x^6+15x^5+44x^3+32x^1"

el código :

function productEncodedPolynoms( sA, sB) {
   var aIndex = 0 ;
   var bIndex = 0 ;
   var resIndex = 0 ;
   var resHash = {} ;
   // for loop within sA, moving 2 items at a time
   for (aIndex = 0; aIndex < sA.length ; aIndex+=2) {
       // for loop within sB, moving 2 items at a time
       for (bIndex = 0; bIndex < sB.length ; bIndex+=2 ) {
           resIndex = sA[aIndex]+sB[bIndex] ;
           // create key/value pair if none created
           if (resHash[resIndex]===undefined)  resHash[resIndex]=0;
           // add this product to right coefficient
           resHash[resIndex] += sA[aIndex+1]*sB[bIndex+1];
       }
   } 
   // now unpack the hash into an encoded sparse array
   // get hash keys
   var coeff = Object.keys(resHash);
   // sort keys in reverse order
   coeff.sort(reverseSort);
   encodedResult = [];
   for (var i=0; i<coeff.length; i++ ) {
     if (resHash[coeff[i]]) {
       encodedResult.push(+coeff[i]);          // (+ converts to int)
       encodedResult.push(+resHash[coeff[i]]);
     }
   }
   return encodedResult;
}

ejemplo:

sA = [ 5, 1, 2, 3, 0, 4 ] ;

sB = [ 6, 2, 3, 5, 1, 8] ;

sAB = productEncodedPolynoms ( sA, sB );

Utilidad para imprimir resultado:

function printEncodedArray(sA) {
  res='''';
  for (var i=0; i<sA.length; i+=2) {
    if (sA[i+1]) {
        if (sA[i+1] != 1 || sA[i]==0) res+=sA[i+1];
        if (sA[i]!=0) res+=''x^''+sA[i];
        if (i!=sA.length-2) res+=''+'';
    }
  }
  return res;
}

// utilities
function reverseSort(a,b) { return b-a ; }

Answer 3

En mi opinión, ni siquiera puede esperar una solución con complejidad O(N*M) debido a la siguiente lógica.

Digamos que las matrices son (a1, a2, a3, a4) y (b1, b2, b3, b4, b5)

Las posibles parejas serán las siguientes:

a1b1 a1b2 a1b3 a1b4 a1b5
     a2b1 a2b2 a2b3 a2b4 a2b5
          a3b1 a3b2 a3b3 a3b4 a3b5
               a4b1 a4b2 a4b3 a4b4 a4b5

Ahora, para cada fila, los pares de la izquierda siempre deben recogerse antes de los pares de la derecha.

1. Así que el primer candidato es a1b1 .
2. Luego, una vez que se a1b1 , los siguientes candidatos son a1b2 y a2b1 .
3. Digamos que a1b2 es elegido. Entonces los candidatos son a1b3 y a2b1 .
4. Ahora digamos que a2b1 es elegido. Entonces los candidatos son a1b3 , a2b2 y a3b1 .

Por lo tanto, vemos que a medida que avanzamos, el número de candidatos para la posición aumenta linealmente.

Por lo tanto, en el peor de los casos, tendrá que realizar comparaciones del orden de N*M*M

Un enfoque O(N*Mlog(M*N)) . (where N = a.size() and M = b.size())

for ( int i = 0; i < a.size(); i++ )
  for ( int j = 0; j < b.size(); j++ )
    sumVector.push_back( a[i] + b[j] );

sort( sumVector ); // using merge sort or quicksort.

Answer 4

Es bastante simple usar un algoritmo para encontrar un par de números en una matriz ordenada que sumen una constante específica K , como se describe en esta pregunta .

Resumen

La solución final sería de complejidad de tiempo O((M+N)*(M+N)) , que es como máximo 4 veces peor que el límite inferior de M*N (solo genera todos los pares). Entonces el factor constante es solo 4.

Edición : Oops, no es O((M+N)*(M+N)) como pensé, aparentemente, es O(K*(M+N)) , donde K es la suma más alta en las dos matrices. No estoy seguro de si este algoritmo se puede mejorar, pero parece que esa solución será similar al método de Transformada Rápida de Fourier descrito por Peter de Rivaz.

Suma en el algoritmo ordenado ordenado

En ese algoritmo, establecemos un puntero inferior a 0 y un puntero superior al final de la matriz. Entonces, si la suma en estas dos posiciones es mayor que K , disminuimos el puntero más alto. Si es más bajo, aumentamos el puntero inferior. Esto funciona porque en cualquier iteración, arr[low] es el elemento más bajo hasta el momento del cual se podría derivar una respuesta. Del mismo modo, arr[high] es el más alto. Entonces, si tomamos los elementos más bajos y más altos, y la suma es mayor que K , sabemos que cualquier otra combinación con arr[high] será mayor que K Así que arr[high] no puede ser parte de ninguna solución. Por lo tanto, podemos eliminarlo de nuestra matriz (esto se logra reduciendo el puntero high ).

Aplicando eso a tu problema

Aplicando esto a su problema, la idea es que iteramos sobre la posible suma, que es de 0 a A[len(A)-1]+B[len(B)-1] . Y para cada suma posible, ejecutamos el algoritmo anterior. Para su problema, establecemos un puntero inferior en la matriz A , y un puntero superior en la matriz B

Para el algoritmo original, se romperá tan pronto como encuentre un par que sume la constante. Para su problema, aumentará ptr_A y disminuirá ptr_B cada uno. Esto funciona porque su matriz está aumentando estrictamente . Entonces, si encontramos que A[ptr_A]+B[ptr_B]==K , entonces A[ptr_A]+B[low_B]<K para todos low_B<ptr_B y A[high_A]+B[ptr_B]>K para todos high_A>ptr_A .

Y esto encontrará todos los pares, porque para cada suma posible K , encontrará todos los pares que suman K , y iteramos sobre toda la suma K posible.

Como beneficio adicional, este algoritmo ordenará la salida en función del aumento del valor en la lista A (puede ordenar en función del aumento del valor en la lista B intercambiando los punteros), y no necesitamos acceso aleatorio a la matriz.

Código en Python

Implementación en Python:

def pair_sum(A,B):
    result = []
    max_sum = A[-1]+B[-1]
    for cur_sum in range(max_sum+1): # Iterate over all possible sum
        ptr_A = 0        # Lower pointer
        ptr_B = len(B)-1 # Higher pointer
        while True:
            if A[ptr_A]+B[ptr_B]>cur_sum:
                ptr_B -= 1
            elif A[ptr_A]+B[ptr_B]<cur_sum:
                ptr_A += 1
            else:
                result.append((A[ptr_A],B[ptr_B]))
                ptr_A += 1
                ptr_B -= 1
            if ptr_A==len(A):
                break
            if ptr_B==-1:
                break
    return result

def main():
    print pair_sum([0,1,2],[1,4])
    print pair_sum([0,1],[0,1])
    print pair_sum([0,1,3],[1,2])

if __name__==''__main__'':
    main()

imprimirá:

[(0, 1), (1, 1), (2, 1), (0, 4), (1, 4), (2, 4)] [(0, 0), (0, 1), (1, 0), (1, 1)] [(0, 1), (0, 2), (1, 1), (1, 2), (3, 1), (3, 2)]

como se desee.

Answer 5

Este problema difiere solo superficialmente de la Clasificación X + Y , una de las principales irritantes para los geometristas computacionales a lo largo de los años. (Consulte el Problema 41 de Joseph O''Rourke (abierto) .) Para resumir ese enlace para los implementadores, el algoritmo más rápido conocido cuando se pueden agregar y comparar los exponentes es O (mn log (mn)), y es el más obvio. Si los exponentes son enteros acotados, entonces se aplica el enfoque de Fourier de Peter. Mucha gente inteligente ha pensado en este problema durante bastante tiempo, por lo que no esperaría un algoritmo mejor en el futuro.

Answer 6

Me pregunto qué tan escasos se espera que sean tus polinomios.

Una opción que vale la pena considerar para la multiplicación de polinomios densos es calcular la transformada de Fourier de los polinomios y multiplicar sus coeficientes de Fourier juntos.

Esto le permite multiplicar polinomios en O (nlogn) donde n es el grado del polinomio.

Esto no sería apropiado para un polinomio disperso como (1 + x ^ 1000000) * (1 + x ^ 1000000) ya que n sería alrededor de 1000000, mientras que el algoritmo actual solo necesitaría algunos ciclos.

Una buena explicación de este enfoque de Fourier se puede encontrar en estas notas de la conferencia .

Answer 7

¿Por qué no generaría la matriz de 2-d sin clasificar y luego usaría una ordenación rápida en ella?

ED: Parece que si generó la matriz final de manera inteligente (utilizando un algoritmo comparativo durante la iteración inicial y la generación de la matriz), más tarde podría usar un algoritmo de clasificación más específico (por ejemplo, smoothsort) y terminar con un rendimiento que se aproxima a O (2 (m * n)) con el peor de los casos de O (m * n + (m * n) log (m * n))

ED2: Estoy absolutamente seguro de que podría escribir un algoritmo para hacer esto en O (m * n). Lo que quieres hacer es generar la matriz limpiamente. No tengo tiempo para escribir el pseudocódigo, pero si tuviera que hacerlo 1. Configure un iterador mínimo, un iterador máximo y un iterador actual para cada una de las matrices, así como una suma máxima actual para ellos . 2. Genere el primer par 3. Iterice una variable, compárela con el otro tercer par posible (guardando eso en una variable temporal) y guárdela en la salida o guarde la otra matriz en la salida y comience de nuevo.

La forma en que lo visualizo es como dos filas de bloques con tres colores: rojo para completamente terminado, azul para "más alto hasta ahora" y sin terminar. Trabaja en una de las filas de bloques a la vez, generando el siguiente valor para la matriz de resultados, comparando siempre la combinación de su línea de base en el lado actual, que es inferior a la suma procesada actualmente. Cada vez que la suma es menor, establece el nuevo resultado más bajo según el resultado que acaba de calcular, agrega el resultado más bajo previamente a su matriz de salida (ya ordenada) y comienza a sumar utilizando el mínimo anterior (y su fila) como línea de base. . Nunca vuelva a entrar en los bloques rojos, y cambie de lado el lado azul cada vez que encuentre un nuevo bajo en el lado opuesto.

Nunca debe calcular un solo resultado dos veces y salir con una matriz ordenada.

Es esencialmente una especie de burbuja flotante. Sabe que el valor calculado es más alto que su suma actual, y hasta que no se procesa registros más bajos en la matriz. Cuando ya no es más alto, cambia su valor superior y vuelve al punto en el que estaba iterando a través de la matriz cuyos miembros son actualmente más pequeños. EX:

A: (1 5 10)

B: (1 6 9)

(1, 1) -> (1, 6) es mayor que (1, 5) así que agregue (1, 5) haga (1, 6) más alto

(5, 6) es más alto que (1, 6) así que agregue (1, 6) haga (5, 6) el movimiento más alto hasta (1, 9)

(1, 9) más bajo que (5, 6) así que [agregue (1, 9) y aumente el acabado en A]

Matriz actual: (1, 1), (1, 5), (1, 6), (1,9)

(1, 10) igual a (5,6) así que agregue ambos, aumente el acabado en B, comience con (5,9)

(5, 9) más alto que (10, 1) así que agregue (10, 1) haga (5, 9) el movimiento más alto hasta (10, 6)

(10, 6) más alto que (5, 9) así que ...

De todos modos Si lo configura correctamente, tiene una única comparación hecha por adición a la matriz final, y puede construirla sobre la marcha sin bifurcar. Si no necesita la matriz final en la memoria en cualquier lugar, las FFT podrían ir más rápido, pero esto debería funcionar.