arrays - matriz - matrices en vba excel
Dado un conjunto, ¿puedo encontrar en O(n) el rango más largo, cuyos puntos finales son los valores más altos en el rango? (7)
Creo que el siguiente algoritmo se ejecuta en el tiempo O (n) y produce una solución óptima. Es un poco complicado, por lo que dividiré la lógica en dos casos, uno en el que consideraremos el caso en el que no hay valores duplicados en el conjunto y otro en el que consideramos que se permiten duplicados.
La estructura de datos clave que usaremos es el árbol cartesiano , que es un montón máximo construido a partir de un rango de datos con la propiedad de que un recorrido inorder de los nodos del árbol produce los valores de la secuencia en el orden en que ellos aparecen El detalle crítico es que es posible construir un árbol cartesiano para una secuencia de elementos en el tiempo O (n).
Como ejemplo, dada la secuencia 4 1 0 3 2, obtendríamos este árbol cartesiano:
4
/
3
/ /
1 2
/
0
Observe que la caminata de inorder realmente devuelve 4 1 0 3 2.
Ahora afirmo que los puntos finales del rango que estamos buscando deben ser un par padre / hijo en el árbol cartesiano (es decir, el primer nodo es uno de los padres del segundo nodo o viceversa). Tenga en cuenta que no estamos buscando un nodo y ningún antecesor, sino específicamente un par padre / hijo. Para probar esto, pruebo las siguientes dos afirmaciones:
Reivindicación 1 : cualquier par padre / hijo en el árbol cartesiano define un rango de valores en la secuencia original que no tiene ningún valor intermedio mayor que los puntos finales.
Reivindicación 2 : Cualquier rango de valores en la secuencia que no tenga ningún valor intermedio mayor que sus puntos finales debe tener esos puntos finales como un par padre / hijo en el árbol cartesiano.
Tomados en conjunto, estos colectivamente demuestran que el rango que estamos buscando debe ser un par padre / hijo en el árbol cartesiano. Esto nos da un algoritmo de tiempo lineal fácil para resolver el problema cuando todos los valores son distintos. Primero, en el tiempo O (n), construye un árbol cartesiano para el rango. A continuación, explore recursivamente el árbol, y para cada par de padres / hijos, encuentre la distancia entre esos pares, tomando el rango más grande que encontremos. Este segundo paso también se ejecuta en O (n), ya que un árbol cartesiano es un árbol binario, por lo que el número de aristas es O (n).
Prueba de la reivindicación uno: una pareja padre / hijo debe verse como cualquiera
u
/
v
/ /
A B
o
u
/
v
/ /
A B
Recuerde que un árbol cartesiano almacena sus elementos de manera que un recorrido de los elementos del árbol proporcione los elementos de la matriz utilizada para producir el árbol en el orden en que aparecen en la matriz. Esto significa que en el caso (1), estamos viendo un rango de elementos que comienzan con u, que contienen todos los A, y concluyen con b. De manera similar, en el caso (2), el rango comienza con v, luego contiene todo B y luego termina con u. Probamos la afirmación de que uyv no tienen valores intermedios que sean más grandes que u u v por contradicción. Supongamos que este fuera el caso y que el valor w es más grande que u u v. Por la definición de un árbol cartesiano, si w está entre uy v en la secuencia original, entonces en el caso (1) debe estar en el subárbol A y en el caso (2) debe estar en el subárbol B. Pero un árbol cartesiano es un montón máximo, y así en el caso (1) ambos uyv son más grandes que todo en A, y en el caso (2) ambos uyv son más grandes que todo en B, una contradicción. Por lo tanto, el rango de valores entre cualquier par padre / hijo no debe ser mayor que el padre o el hijo.
Prueba de la Reivindicación 2: Por contrapositivo; mostramos que si hay una subsecuencia de la matriz original que comienza con u y termina con v que contiene un elemento w más grande que u o v, uyv no puede ser un par padre / hijo o hijo / padre en el árbol cartesiano . La prueba es virtualmente idéntica a la anterior: si uy v fueran un par padre / hijo, entonces en el caso (1) anterior w tendría que estar en A y en el caso (2) w tendría que estar en B, en ambos casos violando el hecho de que un árbol cartesiano es un montón máximo.
Las pruebas anteriores nos muestran que si todos los valores son distintos, podemos resolver este problema en tiempo lineal simplemente construyendo un árbol cartesiano y haciendo una simple caminata por el árbol. Pero, ¿qué sucede si se permite que los elementos sean duplicados, como en el enunciado del problema original? En ese caso, podemos usar una estructura de árbol cartesiano modificado. Permitiremos que los nodos se combinen en un "metanodo" de múltiples valores de árbol cartesianos diferentes que comparten el mismo valor. Por ejemplo, la secuencia 2 7 1 7 8 0 3 8 2 se vería así:
[8 ------- 8]
/ / /
/ 3 2
/ /
/ 0
/
[7 -- 7]
/ /
2 1
Aquí, la raíz es un metanodo que consta de dos nodos con el valor 8, y el primer 8 metanodo consta de dos 7 metanodos.
Para propósitos de notación, permita que el nodo "leftest" de un metanodo sea el nodo más alejado hacia la izquierda en el metanodo, y permita que el nodo "más correcto" de un metanodo sea el nodo más alejado hacia la derecha en un metanodo.
En este árbol cartesiano modificado, podemos definir un recorrido inorden de los nodos como uno que visita todos los nodos en un metanodo en orden de izquierda a derecha, haciendo un recorrido inorder de cada uno de los nodos que contiene. Luego exigimos que el árbol cartesiano modificado sea un max-heap estricto (cada nodo debe ser estrictamente mayor que cualquiera de sus hijos) y que un recorrido inorder del árbol produce los valores en el mismo orden en el que aparecen en la secuencia original.
Observe que esta construcción generalizada contiene nuestra solución original como un caso especial: si todos los valores son distintos, nada es diferente en esta estructura de árbol. También indicaré sin pruebas que es posible construir una de estas estructuras en O (n) mediante una modificación directa del algoritmo de árbol cartesiano estándar.
En esta estructura de árbol modificada, un rango de valores sin valores intermedios al menos tan grandes como los puntos finales corresponde a cualquiera de los siguientes:
- Un padre y el nodo más correcto de su hijo izquierdo.
- Un padre y el nodo más leftest de su hijo correcto.
- Dos nodos adyacentes en el mismo metanodo.
La prueba de los dos primeros reclamos es una modificación directa de la prueba del caso anterior. La diferencia es que en lugar de la prueba de la contradicción que dice que violaría la propiedad de máximo montón, en su lugar, usted alegaría que viola la fuerte propiedad de máximo montón. También diría que cualquier valor igual en el medio del rango tendría que manifestarse a sí mismo como nodos que evitarían que los puntos finales del rango sean los nodos más lentos o más rectos en un metanodo. La prueba de la tercera afirmación es (más o menos) que cualquier nodo entre los dos nodos debe ser estrictamente más pequeño que los puntos finales, y si hubiera un valor igual en el medio, los dos nodos no serían metanodos adyacentes.
Dada esta observación, podemos resolver el problema original en el tiempo O (n) de la siguiente manera. Primero, crea un árbol cartesiano generalizado desde el rango de entrada. Luego, camine por el árbol y observe todos los pares de elementos indicados que podrían ser el rango, escogiendo el más grande que encuentre. Dado que para cada nodo solo se debe verificar un número constante de otros nodos (su padre, hermanos izquierdo y derecho, y los niños dan como máximo cinco nodos para verificar), esto se puede hacer en tiempo O (n) para un tiempo de ejecución neto de En).
¡Uf! Ese fue un gran problema. No sé si esta es una solución ideal, pero al menos demuestra que es posible hacerlo en el tiempo O (n). Si alguien viene con una mejor respuesta, me encantaría verla.
Para una matriz dada de enteros, encuentre la distancia máxima entre 2 puntos (i y j) que tengan valores más altos que cualquier elemento entre ellos.
Ejemplo:
values: 0 10 8 9 6 7 4 10 0 index : 0 1 2 3 4 5 6 7 8
para los valores anteriores, la solución es i = 1, j = 7, pero
- si el valor del índice 7 es 9 en lugar de 10, la solución es i = 3, j = 7
- si el valor del índice 7 es 7 en lugar de 10, la solución es i = 5, j = 7
No puedo ver una solución en O (n) ... ¿alguien?
He escrito una solución para el problema. Hasta ahora parece válido, funciona con todas las entradas que he intentado. Este es el código en C ++. Quería una solución tan simple y clara que pudiera obtenerla, por lo que no sugerí una solución cartesiana o de pila cartesiana, sino un enfoque más simple: analizar primero y obtener la lista de intervalos válidos (como sugirió Rafał Dowgird) y una segunda vez para determinar el intervalo máximo de len que es la solución.
void Solution(const int* vData, int vLen)
{
typedef std::pair Interval;
typedef std::vector ListaIntervaleType;
ListaIntervaleType ListaIntervale;
}
La solución de Rafals es buena, pero podemos prescindir de la pila y así ahorrar algo de memoria. Aquí hay una implementación corta y eficiente en el tiempo O(n) :
def highDist(seq):
res, ltr, rtl = 0, 0, 0
for i in range(len(seq)):
if seq[i] >= seq[ltr]:
res = max(res, i-ltr)
ltr = i
if seq[-i-1] >= seq[-rtl-1]:
res = max(res, i-rtl)
rtl = i
return res
Ejecutar en la entrada de ejemplo:
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 10, 0])
6
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 9, 0])
4
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 7, 0])
2
>>> print highDist([])
0
El truco es que si tenemos dos puntos a y b st todo lo que hay entre ellos es más pequeño que ellos, entonces la distancia máxima que estamos buscando es |ba| o completamente fuera del rango. Por lo tanto, si dividimos toda la secuencia de esa manera, una de ellas es el rango que estamos buscando.
Podemos hacer que la partición cree fácilmente una secuencia ascendente desde cada extremo.
La solución lineal es tranquila y simple. Utilizaremos dos punteros, para las terminaciones del segmento, de modo que cada elemento en él no sea más que el primer elemento. Para el primer elemento fijo (primer puntero) movemos el segundo puntero hacia la derecha hasta que apunta a menor o igual que el primer elemento. Si el elemento en el segundo puntero es grande o igual que el primero, podemos actualizar la respuesta con la longitud del segmento actual. Y si apunta a un elemento estrictamente mayor que el primero, tenemos que mover el primer puntero a la posición actual, porque ningún segmento mo puede comenzar en su última posición: el elemento actual será más que el punto final del segmento.
Este algoritmo encuentra el segmento máximo por longitud con el elemento izquierdo menor o igual que el elemento derecho, por lo que debemos repetir las mismas acciones una vez más, caminando de derecha a izquierda.
Complejidad - O (n), simplemente moviendo n-1 veces el segundo puntero y no más de n-1 veces el primer puntero.
Si mi idea no es clara, haga cualquier pregunta.
No estoy seguro de si la siguiente solución es O (n), pero ciertamente es "casi O (n)", y también muy simple, solo unas pocas líneas de código. Se basa en la siguiente observación. Para cualquier par de índices (i, j), dibuje un arco entre ellos si el intervalo [i, j] tiene la propiedad buscada. Ahora observe que es posible dibujar estos arcos para que no se crucen. Luego observe que los pares más pequeños son (i, i + 1) - todos estos tienen la propiedad buscada. A continuación, un par más grande siempre se puede construir mediante la contracción de dos pares más pequeños. Esto lleva a la siguiente estructura: Comience con los pares (i, i + 1) en una lista vinculada. Revise la lista vinculada repetidamente e intente contratar enlaces consecutivos. Este algoritmo es independiente del orden debido a la propiedad de no intersección. El código de Perl sigue.
#!/usr/local/bin/perl -w
use strict;
my @values = (0, 10, 8, 9, 6, 7, 4, 10, 0); # original example.
@values = map { int(100 * rand()) } 1..100; # random testing.
my $nvalues = @values;
my @intervals = (1..$nvalues-1); # this encodes a linked list 0->1, 1->2, N-2->N-1
my $change = 0;
my ($maxi, $maxj) = (0, 1); # initial solution
my $maxdelta = 1;
do {
my ($jstart, $j) = (0, $intervals[0]);
$change = 0;
while ($j < $nvalues-1) {
my $jnext = $intervals[$j];
while ($jnext < $nvalues -1 && $values[$j] == $values[$jnext]) {
$jnext = $intervals[$jnext]; # lookahead to skip intervals with identical boundaries
}
if ($values[$j] < $values[$jstart] && $values[$j] < $values[$jnext]) {
$intervals[$jstart] = $jnext; # contraction step
print STDERR "contraction to $j $jnext/n";
$change = 1;
$j = $jnext;
if ($jnext - $jstart > $maxdelta) {
$maxdelta = $jnext - $jstart;
($maxi, $maxj) = ($jstart, $jnext);
}
}
else {
($jstart, $j) = ($j, $intervals[$j]);
}
}
print STDERR "---/n";
}
while ($change);
my $jstart = 0;
while ($jstart < $nvalues -1) {
my $jnext = $intervals[$jstart];
local $, = " ";
print STDERR @values[$jstart..$jnext], "/n";
$jstart = $jnext;
}
print STDERR "solution $maxi $maxj/n";
Una simple solución basada en la pila. Itere sobre la matriz de izquierda a derecha, con los elementos que contienen la pila (técnicamente, índices, pero usan valores para las comparaciones) que son:
- El más grande desde la izquierda (es decir, no hay un elemento más grande o igual entre el inicio de la matriz y el elemento)
- El más grande desde el elemento anterior en la pila.
Al procesar el siguiente elemento x , pop elementos más pequeños que x siempre que sean de la categoría 2. anterior, luego presione x en la pila. Obviamente, necesita mantener el máximo actual para poder discernir entre la categoría 2 y 1 en tiempo constante.
El procesamiento anterior es O (n): cada elemento se puede empujar a lo sumo una vez y hacer estallar a lo sumo una vez. Teniendo la pila final, solo revisa los pares vecinos (en la pila): uno de los pares es la solución. Esto también es O (n).
Aquí hay una imagen con lo que debería permanecer en la pila (los rectángulos gordos) después de todo el escaneo de la matriz:
(Hay un pequeño error en la imagen de arriba: la cuarta barra de la izquierda debe ser gruesa o ser más corta que la primera, lo siento)
Por qué esto funciona: la pila final contiene todos los elementos de la matriz de entrada que no están entre dos elementos más grandes (me salté el caso de un elemento entre dos elementos iguales). La solución es obviamente un par vecino de tales elementos.
Aquí hay una implementación en Python:
from collections import namedtuple
E = namedtuple(''E'', ''i x'')
def maxrange(iterable):
stack = [E(0, None)]*2 # push sentinel values
maxsofar = None
top = lambda: stack[-1] # peek at the top element on the stack
for i, x in enumerate(iterable):
while top().x < x and top().x < maxsofar:
stack.pop()
stack.append(E(i, x)) # push
maxsofar = max(maxsofar, x)
return max(b.i-a.i for a,b in zip(stack, stack[1:]))
Ejemplo:
>>> maxrange([2,1,3])
2
ETA: Encontré algunos errores, lo siento. Volveré sobre esto después del trabajo, definitivamente es un problema intrigante.
Escrito en una especie de pseudocódigo; la idea es mover una ventana de tres números sobre la matriz y realizar ciertas comparaciones, luego actualice sus posiciones izquierda y derecha en consecuencia.
// Define the initial window
w1=a[0], w2=a[1], w3=a[2]
// Will hold the length of the current maximum interval
delta_max = 0
// Holds the value of the current interval''s leftmost value
left=max(w1,w2,w3)
// Holds the position of the current interval''s leftmost value
lpos= *position of the chosen wi above*
// Holds the position of the current interval''s rightmost value
rpos = lpos + 1
// Holds the value of the current interval''s rightmost value
right = a[rpos]
i = 0
// Holds the position of the max interval''s leftmost value
lmax = 0
// Holds the position of the max interval''s rightmost value
rmax = 0
while (i<n-3) do
i = i + 3
w1=a[i], w2=a[i+1], w3=a[i+2]
if (w1<left) and (w2<left) and (w3<left)
right = w3
rpos = i + 2
else
// Set the new left to the first value in the window that is bigger than the current left
if (w1>left): left = w1, lpos = i
else
if (w2>left): left = w2, lpos = i+1
else
if (w3>left): left = w3, lpos = i+2
delta = rpos-lpos
if delta>dmax: dmax = delta, lmax = lpos, rmax = rpos
lpos = rpos
rpos = lpos + 1
right = a[rpos]
end