subsecuencia subcadena mas larga creciente comun python algorithm language-agnostic

python - subcadena - La subsecuencia creciente más larga



subsecuencia comun maxima c (9)

Dada una secuencia de entrada, ¿cuál es la mejor manera de encontrar la subsecuencia no decreciente más larga (no necesariamente continua)?

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 # sequence 1, 9, 13, 15 # non-decreasing subsequence 0, 2, 6, 9, 13, 15 # longest non-deceasing subsequence (not unique)

Estoy buscando el mejor algoritmo. Si hay código, Python estaría bien, pero todo está bien.

Acabo de tropezar con este problema, y ​​se me ocurrió esta implementación de Python 3:

def subsequence(seq): if not seq: return seq M = [None] * len(seq) # offset by 1 (j -> j-1) P = [None] * len(seq) # Since we have at least one element in our list, we can start by # knowing that the there''s at least an increasing subsequence of length one: # the first element. L = 1 M[0] = 0 # Looping over the sequence starting from the second element for i in range(1, len(seq)): # Binary search: we want the largest j <= L # such that seq[M[j]] < seq[i] (default j = 0), # hence we want the lower bound at the end of the search process. lower = 0 upper = L # Since the binary search will not look at the upper bound value, # we''ll have to check that manually if seq[M[upper-1]] < seq[i]: j = upper else: # actual binary search loop while upper - lower > 1: mid = (upper + lower) // 2 if seq[M[mid-1]] < seq[i]: lower = mid else: upper = mid j = lower # this will also set the default value to 0 P[i] = M[j-1] if j == L or seq[i] < seq[M[j]]: M[j] = i L = max(L, j+1) # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...] result = [] pos = M[L-1] for _ in range(L): result.append(seq[pos]) pos = P[pos] return result[::-1] # reversing

Como me tomó un tiempo entender cómo funciona el algoritmo, fui un poco prolijo con comentarios, y también agregaré una explicación rápida:

  • seq es la secuencia de entrada.
  • L es un número: se actualiza mientras se repite la secuencia y marca la longitud de la subsecuencia más larga que se haya encontrado hasta ese momento.
  • M es una lista. M[j-1] apuntará a un índice de seq que contiene el valor más pequeño que podría usarse (al final) para construir una subsecuencia creciente de longitud j .
  • P es una lista. P[i] apuntará a M[j] , donde i es el índice de seq . En pocas palabras, indica cuál es el elemento previo de la subsecuencia. P se usa para construir el resultado al final.

Cómo funciona el algoritmo:

  1. Maneje el caso especial de una secuencia vacía.
  2. Comience con una subsecuencia de 1 elemento.
  3. Circule sobre la secuencia de entrada con el índice i .
  4. Con una búsqueda binaria, encuentre la j que permite que seq[M[j] sea < que seq[i] .
  5. Actualiza P , M y L
  6. Traza el resultado y regrésalo al revés.

Nota: Las únicas diferencias con el algoritmo de wikipedia son el desplazamiento de 1 en la lista M , y que X aquí se llama seq . También lo probé con una versión de prueba unitaria ligeramente mejorada de la que se mostró en la respuesta de Eric Gustavson y pasó todas las pruebas.

Ejemplo:

seq = [30, 10, 20, 50, 40, 80, 60] 0 1 2 3 4 5 6 <-- indexes

Al final tendremos:

M = [1, 2, 4, 6, None, None, None] P = [None, None, 1, 2, 2, 4, 4] result = [10, 20, 40, 60]

Como verán, P es bastante sencillo. Tenemos que verlo desde el final, por lo que nos dice que antes de los 60 hay 40, antes de los 80 hay 40 , antes de los 40 hay 20 , antes de los 50 hay 20 y antes de los 20 hay 10 , stop.

La parte complicada es en M Al principio M era [0, None, None, ...] dado que el último elemento de la subsecuencia de longitud 1 (de ahí la posición 0 en M ) estaba en el índice 0: 30 .

En este punto comenzaremos a iterar en seq y miraremos 10 , ya que 10 es < que 30 , M se actualizará:

if j == L or seq[i] < seq[M[j]]: M[j] = i

Entonces ahora M parece: [1, None, None, ...] . Esto es algo bueno, porque 10 tienen más cambios para crear una subsecuencia cada vez más larga. (El nuevo 1 es el índice de 10)

Ahora es el turno de 20 . Con 10 y 20 tenemos una subsecuencia de longitud 2 (índice 1 en M ), por lo que M será: [1, 2, None, ...] . (El nuevo 2 es el índice de 20)

Ahora es el turno de 50 . 50 no será parte de ninguna subsecuencia así que nada cambia.

Ahora es el turno de 40 . Con 10 , 20 y 40 tenemos un sub de longitud 3 (índice 2 en M , entonces M será: [1, 2, 4, None, ...] . (El nuevo 4 es el índice de 40)

Y así...

Para un recorrido completo por el código, puede copiarlo y pegarlo here :)

Aquí es cómo encontrar simplemente la subsecuencia creciente / decreciente más larga en Mathematica:

LIS[list_] := LongestCommonSequence[Sort[list], list]; input={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; LIS[input] -1*LIS[-1*input]

Salida:

{0, 2, 6, 9, 11, 15} {12, 10, 9, 5, 3}

Mathematica también tiene la función de secuencia de aumento más larga en la biblioteca de Combinatorica . Si no tiene Mathematica puede consultar el WolframAlpha .

Solución C ++ O (nlogn)

También hay una solución O (nlogn) basada en algunas observaciones. Deje Ai, j ser la cola más pequeña posible de todas las subsecuencias crecientes de longitud j usando los elementos a 1 , a 2 , ..., a i . Observe que, para cualquier i particular, A i, 1 , A i, 2 , ..., A i, j . Esto sugiere que si queremos la subsecuencia más larga que termina con ai + 1, solo necesitamos buscar aj de tal manera que Ai, j <ai + 1 <= Ai, j + 1 y la longitud será j + 1. Observe que en este caso, Ai + 1, j + 1 será igual a ai + 1, y todo Ai + 1, k será igual a Ai, k para k! = j + 1. Además, hay a lo sumo una diferencia entre el conjunto Ai y el conjunto Ai + 1, que es causado por esta búsqueda. Como A siempre se ordena en orden creciente, y la operación no cambia este orden, podemos hacer una búsqueda binaria para cada uno a 1 , a 2 , ..., a n .

Implementación algoritmo C++ (O (nlogn))

#include <vector> using namespace std; /* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ void find_lis(vector<int> &a, vector<int> &b) { vector<int> p(a.size()); int u, v; if (a.empty()) return; b.push_back(0); for (size_t i = 1; i < a.size(); i++) { if (a[b.back()] < a[i]) { p[i] = b.back(); b.push_back(i); continue; } for (u = 0, v = b.size()-1; u < v;) { int c = (u + v) / 2; if (a[b[c]] < a[i]) u=c+1; else v=c; } if (a[i] < a[b[u]]) { if (u > 0) p[i] = b[u-1]; b[u] = i; } } for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; } /* Example of usage: */ #include <cstdio> int main() { int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }; vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); vector<int> lis; find_lis(seq, lis); for (size_t i = 0; i < lis.size(); i++) printf("%d ", seq[lis[i]]); printf("/n"); return 0; }

Fuente: link

He reescrito la implementación de C ++ en Java hace un tiempo, y puedo confirmar que funciona. La alternativa del vector en python es List. Pero si quiere probarlo usted mismo, aquí hay un enlace para el compilador en línea con la implementación de ejemplo cargada: link

Los datos de ejemplo son: { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 } y respuesta: 1 3 4 5 6 7 .

Aquí está el código y la explicación con Java, puede ser que añadiré para Python pronto.

arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

  1. list = {0} - Inicializa la lista en el conjunto vacío
  2. list = {0,8} - Nuevo LIS más grande
  3. list = {0, 4} - Cambió de 8 a 4
  4. list = {0, 4, 12} - Nueva LIS más grande
  5. list = {0, 2, 12} - Cambió 4 a 2
  6. list = {0, 2, 10} - Cambió de 12 a 10
  7. list = {0, 2, 6} - Cambió de 10 a 6
  8. list = {0, 2, 6, 14} - Nueva LIS más grande
  9. list = {0, 1, 6, 14} - Cambió 2 a 1
  10. list = {0, 1, 6, 9} - Cambió de 14 a 9
  11. list = {0, 1, 5, 9} - Cambió de 6 a 5
  12. list = {0, 1, 6, 9, 13} - Cambió 3 a 2
  13. list = {0, 1, 3, 9, 11} - Nueva LIS más grande
  14. list = {0, 1, 3, 9, 11} - Cambió de 9 a 5
  15. list = {0, 1, 3, 7, 11} - Nueva LIS más grande
  16. list = {0, 1, 3, 7, 11, 15} - Nueva LIS más grande

Entonces, la longitud del LIS es 6 (el tamaño de la lista).

import java.util.ArrayList; import java.util.List; public class LongestIncreasingSubsequence { public static void main(String[] args) { int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; increasingSubsequenceValues(arr); } public static void increasingSubsequenceValues(int[] seq) { List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < seq.length; i++) { int j = 0; boolean elementUpdate = false; for (; j < list.size(); j++) { if (list.get(j) > seq[i]) { list.add(j, seq[i]); list.remove(j + 1); elementUpdate = true; break; } } if (!elementUpdate) { list.add(j, seq[i]); } } System.out.println("Longest Increasing Subsequence" + list); } }

Salida para el código anterior: Mayor subsecuencia de aumento [0, 1, 3, 7, 11, 15]

Aquí hay un código python con pruebas que implementa el algoritmo que se ejecuta en O (n * log (n)). Encontré esto en la página de discusión de wikipedia sobre la subsecuencia creciente más larga .

import unittest def LongestIncreasingSubsequence(X): """ Find and return longest increasing subsequence of S. If multiple increasing subsequences exist, the one that ends with the smallest value is preferred, and if multiple occurrences of that value can end the sequence, then the earliest occurrence is preferred. """ n = len(X) X = [None] + X # Pad sequence so that it starts at X[1] M = [None]*(n+1) # Allocate arrays for M and P P = [None]*(n+1) L = 0 for i in range(1,n+1): if L == 0 or X[M[1]] >= X[i]: # there is no j s.t. X[M[j]] < X[i]] j = 0 else: # binary search for the largest j s.t. X[M[j]] < X[i]] lo = 1 # largest value known to be <= j hi = L+1 # smallest value known to be > j while lo < hi - 1: mid = (lo + hi)//2 if X[M[mid]] < X[i]: lo = mid else: hi = mid j = lo P[i] = M[j] if j == L or X[i] < X[M[j+1]]: M[j+1] = i L = max(L,j+1) # Backtrack to find the optimal sequence in reverse order output = [] pos = M[L] while L > 0: output.append(X[pos]) pos = P[pos] L -= 1 output.reverse() return output # Try small lists and check that the correct subsequences are generated. class LISTest(unittest.TestCase): def testLIS(self): self.assertEqual(LongestIncreasingSubsequence([]),[]) self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1]) self.assertEqual(LongestIncreasingSubsequence(range(10)),range(10)) self.assertEqual(LongestIncreasingSubsequence(/ [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]), [1,2,3,5,8,9]) unittest.main()

Aquí hay una implementación de Python más compacta pero aún eficiente:

def longest_increasing_subsequence_indices(seq): from bisect import bisect_right if len(seq) == 0: return seq # m[j] in iteration i is the last index of the increasing subsequence of seq[:i] # that ends with the lowest possible value while having length j m = [None] * len(seq) predecessor = [None] * len(seq) best_len = 0 for i, item in enumerate(seq): j = bisect_right([seq[k] for k in m[:best_len]], item) m[j] = i predecessor[i] = m[j-1] if j > 0 else None best_len = max(best_len, j+1) result = [] i = m[best_len-1] while i is not None: result.append(i) i = predecessor[i] result.reverse() return result def longest_increasing_subsequence(seq): return [seq[i] for i in longest_increasing_subsequence_indices(seq)]

Aquí hay una solución bastante general que:

  • se ejecuta en el tiempo O(n log n) ,
  • maneja subsecuencias crecientes, no decrecientes, decrecientes y no crecientes,
  • funciona con cualquier objeto de secuencia, incluida list , numpy.array , str y más,
  • admite listas de objetos y métodos de comparación personalizados a través del parámetro key que funciona como el de la función sorted incorporada,
  • puede devolver los elementos de la subsecuencia o sus índices.

El código:

from bisect import bisect_left, bisect_right from functools import cmp_to_key def longest_subsequence(seq, mode=''strictly'', order=''increasing'', key=None, index=False): bisect = bisect_left if mode.startswith(''strict'') else bisect_right # compute keys for comparison just once rank = seq if key is None else map(key, seq) if order == ''decreasing'': rank = map(cmp_to_key(lambda x,y: 1 if x<y else 0 if x==y else -1), rank) rank = list(rank) if not rank: return [] lastoflength = [0] # end position of subsequence with given length predecessor = [None] # penultimate element of l.i.s. ending at given position for i in range(1, len(seq)): # seq[i] can extend a subsequence that ends with a lesser (or equal) element j = bisect([rank[k] for k in lastoflength], rank[i]) # update existing subsequence of length j or extend the longest try: lastoflength[j] = i except: lastoflength.append(i) # remember element before seq[i] in the subsequence predecessor.append(lastoflength[j-1] if j > 0 else None) # trace indices [p^n(i), ..., p(p(i)), p(i), i], where n=len(lastoflength)-1 def trace(i): if i is not None: yield from trace(predecessor[i]) yield i indices = trace(lastoflength[-1]) return list(indices) if index else [seq[i] for i in indices]

Escribí un docstring para la función que no pegué arriba para mostrar el código:

""" Return the longest increasing subsequence of `seq`. Parameters ---------- seq : sequence object Can be any sequence, like `str`, `list`, `numpy.array`. mode : {''strict'', ''strictly'', ''weak'', ''weakly''}, optional If set to ''strict'', the subsequence will contain unique elements. Using ''weak'' an element can be repeated many times. Modes ending in -ly serve as a convenience to use with `order` parameter, because `longest_sequence(seq, ''weakly'', ''increasing'')` reads better. The default is ''strict''. order : {''increasing'', ''decreasing''}, optional By default return the longest increasing subsequence, but it is possible to return the longest decreasing sequence as well. key : function, optional Specifies a function of one argument that is used to extract a comparison key from each list element (e.g., `str.lower`, `lambda x: x[0]`). The default value is `None` (compare the elements directly). index : bool, optional If set to `True`, return the indices of the subsequence, otherwise return the elements. Default is `False`. Returns ------- elements : list, optional A `list` of elements of the longest subsequence. Returned by default and when `index` is set to `False`. indices : list, optional A `list` of indices pointing to elements in the longest subsequence. Returned when `index` is set to `True`. """

Algunos ejemplos:

>>> seq = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] >>> longest_subsequence(seq) [0, 2, 6, 9, 11, 15] >>> longest_subsequence(seq, order=''decreasing'') [12, 10, 9, 5, 3] >>> txt = ("Given an input sequence, what is the best way to find the longest" " (not necessarily continuous) non-decreasing subsequence.") >>> ''''.join(longest_subsequence(txt)) '' ,abdegilnorsu'' >>> ''''.join(longest_subsequence(txt, ''weak'')) '' ceilnnnnrsssu'' >>> ''''.join(longest_subsequence(txt, ''weakly'', ''decreasing'')) ''vuutttttttssronnnnngeee.'' >>> dates = [ ... (''2015-02-03'', ''name1''), ... (''2015-02-04'', ''nameg''), ... (''2015-02-04'', ''name5''), ... (''2015-02-05'', ''nameh''), ... (''1929-03-12'', ''name4''), ... (''2023-07-01'', ''name7''), ... (''2015-02-07'', ''name0''), ... (''2015-02-08'', ''nameh''), ... (''2015-02-15'', ''namex''), ... (''2015-02-09'', ''namew''), ... (''1980-12-23'', ''name2''), ... (''2015-02-12'', ''namen''), ... (''2015-02-13'', ''named''), ... ] >>> longest_subsequence(dates, ''weak'') [(''2015-02-03'', ''name1''), (''2015-02-04'', ''name5''), (''2015-02-05'', ''nameh''), (''2015-02-07'', ''name0''), (''2015-02-08'', ''nameh''), (''2015-02-09'', ''namew''), (''2015-02-12'', ''namen''), (''2015-02-13'', ''named'')] >>> from operator import itemgetter >>> longest_subsequence(dates, ''weak'', key=itemgetter(0)) [(''2015-02-03'', ''name1''), (''2015-02-04'', ''nameg''), (''2015-02-04'', ''name5''), (''2015-02-05'', ''nameh''), (''2015-02-07'', ''name0''), (''2015-02-08'', ''nameh''), (''2015-02-09'', ''namew''), (''2015-02-12'', ''namen''), (''2015-02-13'', ''named'')] >>> indices = set(longest_subsequence(dates, key=itemgetter(0), index=True)) >>> [e for i,e in enumerate(dates) if i not in indices] [(''2015-02-04'', ''nameg''), (''1929-03-12'', ''name4''), (''2023-07-01'', ''name7''), (''2015-02-15'', ''namex''), (''1980-12-23'', ''name2'')]

Esta respuesta fue en parte inspirada por la pregunta en Code Review y en parte por la pregunta sobre valores "fuera de secuencia" .

El algoritmo más eficiente para esto es O (NlogN) delineado aquí .

Otra forma de resolver esto es tomar la subsecuencia común más larga (LCS) de la matriz original y su versión ordenada, que toma el tiempo O (N 2 ).

aquí hay una implementación compacta usando "enumerar"

def lis(l): # we will create a list of lists where each sub-list contains # the longest increasing subsequence ending at this index lis = [[e] for e in l] # start with just the elements of l as contents of the sub-lists # iterate over (index,value) of l for i, e in enumerate(l): # (index,value) tuples for elements b where b<e and a<i lower_tuples = filter(lambda (a,b): b<e, enumerate(l[:i])) # if no such items, nothing to do if not lower_tuples: continue # keep the lis-es of such items lowerlises = [lis[a] for a,b in lower_tuples ] # choose the longest one of those and add # to the current element''s lis lis[i] = max(lowerlises, key=len) + [e] # retrun the longest of lis-es return max(lis, key=len)

int[] a = {1,3,2,4,5,4,6,7}; StringBuilder s1 = new StringBuilder(); for(int i : a){ s1.append(i); } StringBuilder s2 = new StringBuilder(); int count = findSubstring(s1.toString(), s2); System.out.println(s2.reverse()); public static int findSubstring(String str1, StringBuilder s2){ StringBuilder s1 = new StringBuilder(str1); if(s1.length() == 0){ return 0; } if(s2.length() == 0){ s2.append(s1.charAt(s1.length()-1)); findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2); } else if(s1.charAt(s1.length()-1) < s2.charAt(s2.length()-1)){ char c = s1.charAt(s1.length()-1); return 1 + findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2.append(c)); } else{ char c = s1.charAt(s1.length()-1); StringBuilder s3 = new StringBuilder(); for(int i=0; i < s2.length(); i++){ if(s2.charAt(i) > c){ s3.append(s2.charAt(i)); } } s3.append(c); return Math.max(findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2), findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s3)); } return 0; }