algorithm - mas - Cómo encontrar una subsecuencia de longitud mínima que contenga todos los elementos de una secuencia

subsecuencia comun mas larga

Question

Dada una secuencia como S = {1,8,2,1,4,1,2,9,1,8,4}, necesito encontrar la subsecuencia de longitud mínima que contenga todos los elementos de S (sin duplicados, el orden no importa). ¿Cómo encontrar esta subsecuencia de una manera eficiente?

Nota: Hay 5 elementos distintos en S: {1,2,4,8,9}. La subsecuencia de longitud mínima debe contener todos estos 5 elementos.

Answer 1

Aquí hay un algoritmo que requiere O (N) tiempo y O (N) espacio. Es similar a la de Grigor Gevorgyan. También usa una matriz auxiliar de banderas O (N). El algoritmo encuentra la subsecuencia más larga de elementos únicos. Si bestLength < numUnique entonces no hay subsecuencia que contenga todos los elementos únicos. El algoritmo asume que los elementos son números positivos y que el elemento máximo es menor que la longitud de la secuencia.

bool findLongestSequence() {
    // Data (adapt as needed)
    const int N = 13;
    char flags[N];
    int a[] = {1,8,2,1,4,1,2,9,1,8,1,4,1};

    // Number of unique elements
    int numUnique = 0;
    for (int n = 0; n < N; ++n) flags[n] = 0; // clear flags
    for (int n = 0; n < N; ++n) {
        if (a[n] < 0 || a[n] >= N) return false; // assumptions violated 
        if (flags[a[n]] == 0) {
            ++numUnique;
            flags[a[n]] = 1;
        }
    }

    // Find the longest sequence ("best")
    for (int n = 0; n < N; ++n) flags[n] = 0; // clear flags
    int bestBegin = 0, bestLength = 0;
    int begin = 0, end = 0, currLength = 0;
    for (; begin < N; ++begin) {
        while (end < N) {
            if (flags[a[end]] == 0) {
                ++currLength;
                flags[a[end]] = 1;
                ++end;
            }
            else {
                break; // end-loop
            }
        }
        if (currLength > bestLength) {
            bestLength = currLength;
            bestBegin = begin;
        }
        if (bestLength >= numUnique) {
            break; // begin-loop
        }
        flags[a[begin]] = 0; // reset
        --currLength;
    }

    cout << "numUnique = " << numUnique << endl;
    cout << "bestBegin = " << bestBegin << endl;
    cout << "bestLength = " << bestLength << endl;
    return true; // longest subseqence found 
}

Answer 2

Esto se puede resolver mediante programación dinámica .

En cada paso k , calcularemos la subsecuencia más corta que termina en la posición k -ésima de S y que satisface el requisito de contener todos los elementos únicos de S

Dada la solución al paso k (en adelante "la secuencia"), calcular la solución al paso k+1 es fácil: añada el (k+1) -th elemento de S a la secuencia y luego elimine, uno por uno, todos los elementos. al comienzo de la secuencia que están contenidas en la secuencia extendida más de una vez.

La solución al problema general es la secuencia más corta que se encuentra en cualquiera de los pasos.

La inicialización del algoritmo consta de dos etapas:

1. Escanee S una vez, construyendo el alfabeto de valores únicos.
2. Encuentre la secuencia válida más corta cuyo primer elemento sea el primer elemento de S ; La última posición de esta secuencia será el valor inicial de k .

Todo lo anterior se puede hacer en el peor de los casos O(n logn) (hágame saber si esto requiere una aclaración).

Aquí hay una implementación completa del algoritmo anterior en Python:

import collections

S = [1,8,2,1,4,1,2,9,1,8,4,2,4]

# initialization: stage 1
alphabet = set(S)                         # the unique values ("symbols") in S
count = collections.defaultdict(int)      # how many times each symbol appears in the sequence

# initialization: stage 2
start = 0
for end in xrange(len(S)):
  count[S[end]] += 1
  if len(count) == len(alphabet):         # seen all the symbols yet?
    break
end += 1

best_start = start
best_end = end

# the induction
while end < len(S):
  count[S[end]] += 1
  while count[S[start]] > 1:
    count[S[start]] -= 1
    start += 1
  end += 1
  if end - start < best_end - best_start: # new shortest sequence?
    best_start = start
    best_end = end

print S[best_start:best_end]

Notas:

1. Las estructuras de datos que utilizo (diccionarios y conjuntos) se basan en tablas hash; tienen un buen rendimiento promedio, pero pueden degradarse a O(n) en el peor de los casos. Si es el peor de los casos que le importa, reemplazarlos con estructuras basadas en árboles proporcionará la O(n logn) que he prometido anteriormente;
2. Como lo señaló @biziclop, se puede eliminar el primer escaneo de S , haciendo que el algoritmo sea adecuado para la transmisión de datos;
3. Si los elementos de S son enteros no negativos pequeños, como lo indican sus comentarios, entonces el count se puede aplanar en una matriz de enteros, reduciendo la complejidad general a O(n) .

Answer 3

La solución anterior es correcta y la versión java del código anterior.

public class MinSequence {

    public static void main(String[] args)
    {
        final int n; // the size of array
        // read n and the array
        final List<Integer> arr=new ArrayList<Integer>(4);
        Map<Integer, Integer> cur = new TreeMap<Integer, Integer>();
        arr.add(1);
        arr.add(2);
        arr.add(1);
        arr.add(3);
        int distinctcount=0;
        for (final Integer integer : arr)
        {
            if(cur.get(integer)==null)
            {
                cur.put(integer, 1);
                ++distinctcount;
            }else
            {
                cur.put(integer,cur.get(integer)+1);
            }
        }

        // now k is the number of distinct elements
        cur=new TreeMap<Integer,Integer>();
        //   memset( cur, 0, sizeof( cur )); // we need this array anew
        int begin = 0, end = -1; // to make it 0 after first increment
        int best = -1; // best answer currently found
        int ansbegin = 0, ansend = 0; // interval of the best answer currently found
        int cnt = 0; // distinct elements in current subsequence
        final int inpsize = arr.size();
        while(true)
        {
            if( cnt < distinctcount )
            {
                ++end;
                if (end == inpsize) {
                    break;
                }
                if( cur.get(arr.get(end)) == null ) {
                    ++cnt;
                    cur.put(arr.get(end), 1);
                } // this elements wasn''t present in current subsequence;
                else
                {
                    cur.put(arr.get(end),cur.get(arr.get(end))+1);
                }
                continue;
            }
            // if we''re here it means that [begin, end] interval contains all distinct elements
            // try to shrink it from behind
            while (cur.get(arr.get(begin)) != null && cur.get(arr.get(begin)) > 1) // we have another such element later in the subsequence
            {
                cur.put(arr.get(begin),cur.get(arr.get(begin))-1);
                ++begin;
            }
            // now, compare [begin, end] with the best answer found yet
            if( best == -1 || end - begin < best )
            {
                best = end - begin;
                ansbegin = begin;
                ansend = end;
            }
            // now increment the begin iterator to make cur < k and begin increasing the end iterator again
            if (cur.get(arr.get(begin)) != null) {
                cur.put(arr.get(begin),cur.get(arr.get(begin))-1);
            }
            ++begin;
            --cnt;
        }

        // output the [ansbegin, ansend] interval as it''s the answer to the problem
        System.out.println(ansbegin+"--->"+ansend);
        for( int i = ansbegin; i <= ansend; ++i ) {
            System.out.println(arr.get(i));
        }
    }

Answer 4

Si necesita hacer esto con bastante frecuencia para la misma secuencia y diferentes conjuntos, puede usar las listas invertidas para esto. Usted prepara las listas invertidas para la secuencia y luego recopila todas las compensaciones. Luego escanee los resultados de las listas invertidas para una secuencia de m números secuenciales.

Con n la longitud de la secuencia y m el tamaño de la consulta, la preparación estaría en O(n) . El tiempo de respuesta para la consulta sería en O(m^2) si no estoy calculando mal el paso de combinación.

Si necesita más detalles, consulte el documento de Clausen / Kurth de 2004 sobre bases de datos algebraicas (" Recuperación de información basada en contenido por métodos teóricos de grupo "). Este esboza un marco de base de datos general que puede adaptarse a su tarea.

Answer 5

Tengo un algoritmo O (N * M) donde N es la longitud de S, y M es el número de elementos (tiende a funcionar mejor para valores pequeños de M, es decir: si hay muy pocos duplicados, puede ser un mal algoritmo con costo cuadrático) Editar: Parece que, de hecho, está mucho más cerca de O (N) en la práctica . Obtiene O(N*M) solo en el peor de los casos

Comience por recorrer la secuencia y registre todos los elementos de S. Llamemos a este conjunto E.

Vamos a trabajar con una subsecuencia dinámica de S. Cree un map vacío M donde M se asocia a cada elemento el número de veces que está presente en la subsecuencia.

Por ejemplo, si subSequence = {1,8,2,1,4} , y E = {1, 2, 4, 8, 9}

• M[9]==0
• M[2]==M[4]==M[8]==1
• M[1]==2

Necesitará dos índices, cada uno de los cuales apuntará a un elemento de S. Uno de ellos se llamará L porque está a la izquierda de la subsecuencia formada por esos dos índices. El otro se llamará R, ya que es el índice de la parte derecha de la subsecuencia.

Comience por inicializar L=0 , R=0 y M[S[0]]++

El algoritmo es:

While(M does not contain all the elements of E)
{
    if(R is the end of S)
      break
  R++
  M[S[R]]++ 
}
While(M contains all the elements of E)
{
  if(the subsequence S[L->R] is the shortest one seen so far)
    Record it
  M[S[L]]--
  L++
}

Para verificar si M contiene todos los elementos de E, puede tener un vector de booleanos V. V[i]==true si M[E[i]]>0 y V[i]==false si M[E[i]]==0 . Entonces comienzas por configurar todos los valores de V en false , y cada vez que haces M[S[R]]++ , puedes establecer V de este elemento en true , y cada vez que lo haces M[S[L]]-- y M[S[L]]==0 luego, establezca V de este elemento en false

Answer 6

Yo diría que:

1. Construye el conjunto de elementos D.
2. Mantenga una matriz con el mismo tamaño que su secuencia S.
3. Rellene la matriz con índices desde S que indican el último inicio de una secuencia con todos los elementos de D que terminan en ese índice.
4. Encuentre la longitud mínima de las secuencias en la matriz y guarde la posición para el inicio y el final.

Obviamente, solo el artículo 3. es complicado. Usaría una cola / montón de prioridad que asigna una clave a cada elemento desde D y tiene el elemento como valor. Aparte de eso, querrá una estructura de datos que sea capaz de acceder a los elementos en el montón por su valor (mapa w / punteros a los elementos). La clave siempre debe ser la última posición en S en la que se ha producido el elemento.

Así que pasa por S y para cada char que lees, haces una de setKey O (log n) y luego miras el min O (1) actual y lo escribes en la matriz.

Debería ser O (n * log n). Espero no haberme perdido nada. Me vino a la mente, así que tómelo con un grano de sal, o deje que la comunidad señale los posibles errores que podría haber cometido.

Answer 7

Algoritmo:

Primero, determine la cantidad de diferentes elementos en la matriz, esto se puede hacer fácilmente en tiempo lineal. Que haya k elementos diferentes.

Asigne una cur de matriz de tamaño 10 ^ 5, cada una muestra la cantidad de cada elemento que se utiliza en la subsecuencia actual (ver más adelante).

Mantenga una variable cnt que muestre cuántos elementos diferentes hay actualmente en la secuencia considerada. Ahora, tome dos índices, begin y end e itérelos a través de la matriz de la siguiente manera:

1. inicialice cnt y begin como 0 , end como -1 (para obtener 0 después del primer incremento). Entonces, mientras sea posible, realizar lo siguiente:

2. Si cnt != k :

   2.1. incremento end Si el end ya es el final de la matriz, entonces rompa. Si cur[array[end]] es cero, incremente cnt . Incremento cur[array[end]] .

   Más:

   2.2 {

   Intente incrementar el iterador de begin : while cur[array[begin]] > 1 , lo decrementa e incrementa el begin ( cur[array[begin]] > 1 significa que tenemos otro elemento similar en nuestra subsecuencia actual). Después de todo, compare el intervalo [begin, end] con la respuesta actual y guárdelo si es mejor.

   }

Después de que el proceso adicional se vuelve imposible, tienes la respuesta. La complejidad es O(n) : solo se pasan dos interator a través de la matriz.

Implementación en C ++:

    #include <iostream>

using namespace std;

const int MAXSIZE = 10000;

int arr[ MAXSIZE ];
int cur[ MAXSIZE ];

int main ()
{
   int n; // the size of array
   // read n and the array

   cin >> n;
   for( int i = 0; i < n; ++i )
      cin >> arr[ i ];

   int k = 0;
   for( int i = 0; i < n; ++i )
   {
      if( cur[ arr[ i ] ] == 0 )
         ++k;
      ++cur[ arr[ i ] ];
   }

   // now k is the number of distinct elements

   memset( cur, 0, sizeof( cur )); // we need this array anew
   int begin = 0, end = -1; // to make it 0 after first increment
   int best = -1; // best answer currently found
   int ansbegin, ansend; // interval of the best answer currently found
   int cnt = 0; // distinct elements in current subsequence

   while(1)
   {
      if( cnt < k )
      {
         ++end;
         if( end == n )
            break;
         if( cur[ arr[ end ]] == 0 )
            ++cnt; // this elements wasn''t present in current subsequence;
         ++cur[ arr[ end ]];
         continue;
      }
      // if we''re here it means that [begin, end] interval contains all distinct elements
      // try to shrink it from behind
      while( cur[ arr[ begin ]] > 1 ) // we have another such element later in the subsequence
      {
         --cur[ arr[ begin ]];
         ++begin;
      }
      // now, compare [begin, end] with the best answer found yet
      if( best == -1 || end - begin < best )
      {
         best = end - begin;
         ansbegin = begin;
         ansend = end;
      }
      // now increment the begin iterator to make cur < k and begin increasing the end iterator again
      --cur[ arr[ begin]];
      ++begin;
      --cnt;
   }

   // output the [ansbegin, ansend] interval as it''s the answer to the problem

   cout << ansbegin << '' '' << ansend << endl;
   for( int i = ansbegin; i <= ansend; ++i )
      cout << arr[ i ] << '' '';
   cout << endl;

   return 0;
}