algorithm - nlogn - longest increasing subsequence with binary search

Número de subsecuencias cada vez más largas

Question

Estoy practicando algoritmos y una de mis tareas es contar el número de sub secuencias más extensas para números dados 0 <n <= 10 ^ 6 . La solución O (n ^ 2) no es una opción.

Ya he implementado la búsqueda de un LIS y su longitud ( Algoritmo LIS ), pero este algoritmo cambia los números al mínimo posible. Por lo tanto, es imposible determinar si las subsecuencias con un número anterior (el más grande) serían capaces de alcanzar la longitud más larga, de lo contrario, podría contar esos interruptores, supongo.

¿Alguna idea de cómo obtener esto sobre O (nlogn) ? Sé que debería resolverse usando programación dinámica.

Implementé una solución y funciona bien, pero requiere dos bucles anidados (i en 1..n) x (j en 1..i-1) .
Así que es O (n ^ 2) Creo que, sin embargo, es demasiado lento.

Intenté incluso mover esos números de la matriz a un árbol binario (porque en cada iteración busco todos los números más pequeños, luego el número [i] - yendo a través de los elementos i-1..1 ), pero fue incluso más lento.

Pruebas de ejemplo:

1 3 2 2 4
result: 3 (1,3,4 | 1,2,4 | 1,2,4)
3 2 1
result: 3 (1 | 2 | 3)
16 5 8 6 1 10 5 2 15 3 2 4 1
result: 3 (5,8,10,15 | 5,6,10,15 | 1,2,3,4)

Answer 1

Encontrar el número de subsecuencias cada vez más largas

El código completo de Java del algoritmo LIS mejorado, que descubre no solo la longitud de la subsecuencia creciente más larga, sino también el número de subsecuencias de dicha longitud, está debajo. Prefiero usar genéricos para permitir no solo enteros, sino también cualquier tipo comparable.

@Test
public void testLisNumberAndLength() {
List<Integer> input = Arrays.asList(16, 5, 8, 6, 1, 10, 5, 2, 15, 3, 2, 4, 1);
int[] result = lisNumberAndlength(input);
System.out.println(String.format(
"This sequence has %s longest increasing subsequenses of length %s",
result[0], result[1]
));
}
/**
* Body of improved LIS algorithm
*/
public <T extends Comparable<T>> int[] lisNumberAndLength(List<T> input) {
if (input.size() == 0)
return new int[] {0, 0};
List<List<Sub<T>>> subs = new ArrayList<>();
List<Sub<T>> tails = new ArrayList<>();
for (T e : input) {
int pos = search(tails, new Sub<>(e, 0), false); // row for a new sub to be placed
int sum = 1;
if (pos > 0) {
List<Sub<T>> pRow = subs.get(pos - 1); // previous row
int index = search(pRow, new Sub<T>(e, 0), true); // index of most left element that <= e
if (pRow.get(index).value.compareTo(e) < 0) {
index--;
}
sum = pRow.get(pRow.size() - 1).sum; // sum of tail element in previous row
if (index >= 0) {
sum -= pRow.get(index).sum;
}
}
if (pos >= subs.size()) { // add a new row
List<Sub<T>> row = new ArrayList<>();
row.add(new Sub<>(e, sum));
subs.add(row);
tails.add(new Sub<>(e, 0));
} else { // add sub to existing row
List<Sub<T>> row = subs.get(pos);
Sub<T> tail = row.get(row.size() - 1);
if (tail.value.equals(e)) {
tail.sum += sum;
} else {
row.add(new Sub<>(e, tail.sum + sum));
tails.set(pos, new Sub<>(e, 0));
}
}
}
List<Sub<T>> lastRow = subs.get(subs.size() - 1);
Sub<T> last = lastRow.get(lastRow.size() - 1);
return new int[]{last.sum, subs.size()};
}
/**
* Implementation of binary search in a sorted list
*/
public <T> int search(List<? extends Comparable<T>> a, T v, boolean reversed) {
if (a.size() == 0)
return 0;
int sign = reversed ? -1 : 1;
int right = a.size() - 1;
Comparable<T> vRight = a.get(right);
if (vRight.compareTo(v) * sign < 0)
return right + 1;
int left = 0;
int pos = 0;
Comparable<T> vPos;
Comparable<T> vLeft = a.get(left);
for(;;) {
if (right - left <= 1) {
if (vRight.compareTo(v) * sign >= 0 && vLeft.compareTo(v) * sign < 0)
return right;
else
return left;
}
pos = (left + right) >>> 1;
vPos = a.get(pos);
if (vPos.equals(v)) {
return pos;
} else if (vPos.compareTo(v) * sign > 0) {
right = pos;
vRight = vPos;
} else {
left = pos;
vLeft = vPos;
}
}
}
/**
* Class for ''sub'' pairs
*/
public static class Sub<T extends Comparable<T>> implements Comparable<Sub<T>> {
T value;
int sum;
public Sub(T value, int sum) {
this.value = value;
this.sum = sum;
}
@Override public String toString() {
return String.format("(%s, %s)", value, sum);
}
@Override public int compareTo(Sub<T> another) {
return this.value.compareTo(another.value);
}
}

Explicación

Como mi explicación parece ser larga, llamaré a la secuencia inicial "seq" y a cualquiera de sus subsecuencias "sub". Por lo tanto, la tarea es calcular el recuento de los subs más largos que se pueden obtener a partir de la secuencia.

Como mencioné anteriormente, la idea es mantener conteos de todos los subs más largos obtenidos en los pasos anteriores. Así que creemos una lista numerada de filas, donde el número de cada línea es igual a la longitud de los subs almacenados en esta fila . Y almacenemos los subs como pares de números (v, c), donde "v" es "valor" del elemento final , "c" es "recuento" de subs de longitud determinada que termina por "v" . Por ejemplo:

1: (16, 1) // that means that so far we have 1 sub of length 1 which ends by 16.

Construiremos dicha lista paso a paso, tomando elementos de la secuencia inicial por orden. En cada paso trataremos de agregar este elemento al sub más largo al que se puede agregar y registrar los cambios.

Construyendo una lista

Construyamos la lista usando la secuencia de su ejemplo, ya que tiene todas las opciones posibles:

 16 5 8 6 1 10 5 2 15 3 2 4 1

Primero, toma el elemento 16 . Nuestra lista está vacía hasta el momento, así que solo ponemos un par en ella:

1: (16, 1) <= one sub that ends by 16

El siguiente es 5 . No se puede agregar a un sub que termina en 16, por lo que creará un nuevo sub con una longitud de 1. Creamos un par (5, 1) y lo ponemos en la línea 1:

1: (16, 1)(5, 1)

El elemento 8 viene después. No puede crear el sub [16, 8] de longitud 2, pero puede crear el sub [5, 8]. Entonces, aquí es donde viene el algoritmo. Primero, iteramos las filas de la lista al revés, mirando los "valores" del último par. Si nuestro elemento es mayor que los valores de todos los últimos elementos en todas las filas, entonces podemos agregarlo a sub (s) existentes, aumentando su longitud en uno. Entonces el valor 8 creará una nueva fila de la lista, porque es mayor que todos los últimos elementos existentes en la lista (es decir,> 5):

1: (16, 1)(5, 1)
2: (8, ?) <=== need to resolve how many longest subs ending by 8 can be obtained

El elemento 8 puede continuar 5, pero no puede continuar 16. Por lo tanto, debemos buscar en la fila anterior, empezando desde su final, calcular la suma de "recuentos" en pares cuyo "valor" es menor que 8:

(16, 1)(5, 1)^ // sum = 0
(16, 1)^(5, 1) // sum = 1
^(16, 1)(5, 1) // value 16 >= 8: stop. count = sum = 1, so write 1 in pair next to 8
1: (16, 1)(5, 1)
2: (8, 1) <=== so far we have 1 sub of length 2 which ends by 8.

¿Por qué no almacenamos el valor 8 en subs de longitud 1 (primera línea)? Porque necesitamos subs de la máxima longitud posible, y 8 pueden continuar algunos subs previos. Por lo tanto, cada número siguiente mayor a 8 también continuará tal sub y no hay necesidad de mantener 8 como sub de longitud menor de lo que puede ser.

Siguiente. 6 . Búsqueda al revés por los últimos "valores" en las filas:

1: (16, 1)(5, 1) <=== 5 < 6, go next
2: (8, 1)
1: (16, 1)(5, 1)
2: (8, 1 ) <=== 8 >= 6, so 6 should be put here

Encontré el cuarto para 6, necesito calcular un conteo:

take previous line
(16, 1)(5, 1)^ // sum = 0
(16, 1)^(5, 1) // 5 < 6: sum = 1
^(16, 1)(5, 1) // 16 >= 6: stop, write count = sum = 1
1: (16, 1)(5, 1)
2: (8, 1)(6, 1)

Después de procesar 1 :

1: (16, 1)(5, 1)(1, 1) <===
2: (8, 1)(6, 1)

Después de procesar 10 :

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)
3: (10, 2) <=== count is 2 because both "values" 8 and 6 from previous row are less than 10, so we summarized their "counts": 1 + 1

Después de procesar 5 :

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1) <===
3: (10, 2)

Después del procesamiento 2 :

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1) <===
3: (10, 2)

Después del procesamiento 15 :

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)
4: (15, 2) <===

Después de procesar 3 :

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)(3, 1) <===
4: (15, 2)

Después del procesamiento 2 :

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2) <===
3: (10, 2)(3, 1)
4: (15, 2)

Si al buscar filas por el último elemento encontramos un elemento igual, calculamos su "recuento" de nuevo en base a la fila anterior, y lo agregamos al "recuento" existente.

Después de procesar 4 :

1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2)
3: (10, 2)(3, 1)
4: (15, 2)(4, 1) <===

Después de procesar 1 :

1: (16, 1)(5, 1)(1, 2) <===
2: (8, 1)(6, 1)(5, 1)(2, 2)
3: (10, 2)(3, 1)
4: (15, 2)(4, 1)

Entonces, ¿qué tenemos después de procesar toda la secuencia inicial? Mirando la última fila, vemos que tenemos 3 subs más largos, cada uno consta de 4 elementos: 2 terminan por 15 y 1 termina por 4.

¿Qué pasa con la complejidad?

En cada iteración, al tomar el siguiente elemento de la secuencia inicial, hacemos 2 bucles: primero al iterar filas para encontrar espacio para el siguiente elemento, y el segundo al resumir los recuentos en la fila anterior. Por lo tanto, para cada elemento maximizamos n iteraciones (en el peor de los casos: si el seq inicial consta de elementos en orden creciente, obtendremos una lista de n filas con 1 par en cada fila; si se ordena en orden descendente, obtendremos lista de 1 fila con n elementos). Por cierto, la complejidad O (n ² ) no es lo que queremos.

Primero, esto es obvio, que en cada estado intermedio las filas se ordenan por orden creciente de su último "valor". Entonces, en lugar de un bucle bruto, se puede realizar una búsqueda binaria, cuya complejidad es O (log n).

En segundo lugar, no necesitamos resumir los "recuentos" de subs realizando un bucle a través de los elementos de la fila cada vez. Podemos resumirlos en proceso, cuando se agrega un nuevo par a la fila, como:

1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row

Entonces, el segundo número mostrará el conteo de los subs más largos que se pueden obtener con el valor dado al final, pero el recuento de resumen de todos los subs más largos que terminan por cualquier elemento que sea mayor o igual que "valor" del par.

Por lo tanto, "conteos" serán reemplazados por "sumas". Y en lugar de iterar elementos en la fila anterior, simplemente realizamos la búsqueda binaria (es posible porque los pares en cualquier fila siempre están ordenados por sus "valores") y tomamos "suma" para el nuevo par como "suma" del último elemento en la fila anterior menos "suma" del elemento dejado para encontrar la posición en la fila anterior más "suma" del elemento anterior en la fila actual.

Entonces al procesar 4 :

1: (16, 1)(5, 2)(1, 3)
2: (8, 1)(6, 2)(5, 3)(2, 5)
3: (10, 2)(3, 3)
4: (15, 2) <=== room for (4, ?)
search in row 3 by "values" < 4:
3: (10, 2)^(3, 3)

4 se emparejará con (3-2 + 2): ("suma" desde el último par de la fila anterior) - ("suma" desde el par de la posición izquierda a la posición encontrada en la fila anterior) + ("suma" del par anterior en la corriente fila):

4: (15, 2)(4, 3)

En este caso, el recuento final de todos los subs más largos es "suma" desde el último par de la última fila de la lista, es decir, 3, no 3 + 2.

Por lo tanto, al realizar una búsqueda binaria tanto en búsqueda de fila como en búsqueda de suma, llegaremos con complejidad O (n * log n).

En cuanto a la memoria consumida, después de procesar todas las matrices obtenemos un máximo de n pares, por lo que el consumo de memoria en el caso de las matrices dinámicas será O (n). Además, cuando se utilizan conjuntos o colecciones dinámicas, se necesita un tiempo adicional para asignarlos y redimensionarlos, pero la mayoría de las operaciones se realizan en tiempo O (1) porque no realizamos ningún tipo de clasificación y reorganización durante el proceso. Entonces la estimación de complejidad parece ser final.

Answer 2

La respuesta de Sasha Salauyou es genial, pero no tengo claro por qué

sum -= pRow.get(index).sum;

aquí está mi código basado en la misma idea

import java.math.BigDecimal;
import java.util.*;
class lisCount {
static BigDecimal lisCount(int[] a) {
class Container {
Integer v;
BigDecimal count;
Container(Integer v) {
this.v = v;
}
}
List<List<Container>> lisIdxSeq = new ArrayList<List<Container>>();
int lisLen, lastIdx;
List<Container> lisSeqL;
Container lisEle;
BigDecimal count;
int pre;
for (int i = 0; i < a.length; i++){
pre = -1;
count = new BigDecimal(1);
lisLen = lisIdxSeq.size();
lastIdx = lisLen - 1;
lisEle = new Container(i);
if(lisLen == 0 || a[i] > a[lisIdxSeq.get(lastIdx).get(0).v]){
// lis len increased
lisSeqL = new ArrayList<Container>();
lisSeqL.add(lisEle);
lisIdxSeq.add(lisSeqL);
pre = lastIdx;
}else{
int h = lastIdx;
int l = 0;
while(l < h){
int m = (l + h) / 2;
if(a[lisIdxSeq.get(m).get(0).v] < a[i]) l = m + 1;
else h = m;
}
List<Container> lisSeqC = lisIdxSeq.get(l);
if(a[i] <= a[lisSeqC.get(0).v]){
int hi = lisSeqC.size() - 1;
int lo = 0;
while(hi < lo){
int mi = (hi + lo) / 2;
if(a[lisSeqC.get(mi).v] < a[i]) lo = mi + 1;
else hi = mi;
}
lisSeqC.add(lo, lisEle);
pre = l - 1;
}
}
if(pre >= 0){
Iterator<Container> it = lisIdxSeq.get(pre).iterator();
count = new BigDecimal(0);
while(it.hasNext()){
Container nt = it.next();
if(a[nt.v] < a[i]){
count = count.add(nt.count);
}else break;
}
}
lisEle.count = count;
}
BigDecimal rst = new BigDecimal(0);
Iterator<Container> i = lisIdxSeq.get(lisIdxSeq.size() - 1).iterator();
while(i.hasNext()){
rst = rst.add(i.next().count);
}
return rst;
}
public static void main(String[] args) {
System.out.println(lisCount(new int[] { 1, 3, 2, 2, 4 }));
System.out.println(lisCount(new int[] { 3, 2, 1 }));
System.out.println(lisCount(new int[] { 16, 5, 8, 6, 1, 10, 5, 2, 15, 3, 2, 4, 1 }));
}
}

Answer 3

La clasificación por paciencia también es O (N * logN), pero mucho más corta y simple que los métodos basados ​​en la búsqueda binaria:

static int[] input = {4, 5, 2, 8, 9, 3, 6, 2, 7, 8, 6, 6, 7, 7, 3, 6};
/**
* Every time a value is tested it either adds to the length of LIS (by calling decs.add() with it), or reduces the remaining smaller cards that must be found before LIS consists of smaller cards. This way all inputs/cards contribute in one way or another (except if they''re equal to the biggest number in the sequence; if want''t to include in sequence, replace ''card <= decs.get(decIndex)'' with ''card < decs.get(decIndex)''. If they''re bigger than all decs, they add to the length of LIS (which is something we want), while if they''re smaller than a dec, they replace it. We want this, because the smaller the biggest dec is, the smaller input we need before we can add onto LIS.
*
* If we run into a decreasing sequence the input from this sequence will replace each other (because they''ll always replace the leftmost dec). Thus this algorithm won''t wrongfully register e.g. {2, 1, 3} as {2, 3}, but rather {2} -> {1} -> {1, 3}.
*
* WARNING: This can only be used to find length, not actual sequence, seeing how parts of the sequence will be replaced by smaller numbers trying to make their sequence dominate
*
* Due to bigger decs being added to the end/right of ''decs'' and the leftmost decs always being the first to be replaced with smaller decs, the further a dec is to the right (the bigger it''s index), the bigger it must be. Thus, by always replacing the leftmost decs, we don''t run the risk of replacing the biggest number in a sequence (the number which determines if more cards can be added to that sequence) before a sequence with the same length but smaller numbers (thus currently equally good, due to length, and potentially better, due to less needed to increase length) has been found.
*/
static void patienceFindLISLength() {
ArrayList<Integer> decs = new ArrayList<>();
inputLoop: for (Integer card : input) {
for (int decIndex = 0; decIndex < decs.size(); decIndex++) {
if (card <= decs.get(decIndex)) {
decs.set(decIndex, card);
continue inputLoop;
}
}
decs.add(card);
}
System.out.println(decs.size());
}