Encuentra la ventana más pequeña de la matriz de entrada que contiene todos los elementos de la matriz de consulta

Question

Problema: Dada una matriz de entrada de enteros de tamaño ny una matriz de consulta de enteros de tamaño k, encuentre la ventana más pequeña de la matriz de entrada que contenga todo los elementos de la matriz de consulta y también en el mismo orden.

He intentado a continuación.

 int[] inputArray = new int[] { 2, 5, 2, 8, 0, 1, 4, 7 }; 
     int[] queryArray = new int[] { 2, 1, 7 }; 

Encontrará la posición de todos los elementos del conjunto de consultas en inputArray.

public static void SmallestWindow(int[] inputArray, int[] queryArray) 
    { 
     Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>(); 

     int index = 0; 
     foreach (int i in queryArray) 
     { 
      HashSet<int> hash = new HashSet<int>(); 
      foreach (int j in inputArray) 
      { 
       index++; 
       if (i == j) 
        hash.Add(index); 
      } 
      dict.Add(i, hash); 
      index = 0; 
     } 
     // Need to perform action in above dictionary.?? 
    } 

Me siguiente diccionario

1. int 2 -> Posición {1, 3}
2. int 1 -> Posición {6}
3. int 7 -> Posición { 8}

Ahora quiero llevar a cabo después de la etapa findout ventana mínima

1. Comparar la posición int 2 con la posición int 1. Como (6-3) < (6-1) .. Así que voy a almacenar 3, 6 en un hashmap.

2. Comparará la posición de int 1 e int 7 igual que arriba.

No puedo entender cómo voy a comparar dos valores consecutivos de un diccionario. Por favor ayuda.

Answer 1

No veo cómo usar HashSet y Dictionary te ayudará en esto. Si tuviera que enfrentar este problema, lo haría de manera bastante diferente.

Una forma de hacerlo (no la manera más eficiente) se muestra a continuación. Este código supone que queryArray contiene al menos dos elementos.

int FindInArray(int[] a, int start, int value) 
{ 
    for (int i = start; i < a.Length; ++i) 
    { 
     if (a[i] == value) 
      return i; 
    } 
    return -1; 
} 

struct Pair 
{ 
    int first; 
    int last; 
} 

List<Pair> foundPairs = new List<Pair>(); 

int startPos = 0; 
bool found = true; 
while (found) 
{ 
    found = false; 
    // find next occurrence of queryArray[0] in inputArray 
    startPos = FindInArray(inputArray, startPos, queryArray[0]); 
    if (startPos == -1) 
    { 
     // no more occurrences of the first item 
     break; 
    } 
    Pair p = new Pair(); 
    p.first = startPos; 
    ++startPos; 
    int nextPos = startPos; 
    // now find occurrences of remaining items 
    for (int i = 1; i < queryArray.Length; ++i) 
    { 
     nextPos = FindInArray(inputArray, nextPos, queryArray[i]); 
     if (nextPos == -1) 
     { 
      break; // didn't find it 
     } 
     else 
     { 
      p.last = nextPos++; 
      found = (i == queryArray.Length-1); 
     } 
    } 
    if (found) 
    { 
     foundPairs.Add(p); 
    } 
} 

// At this point, the foundPairs list contains the (start, end) of all 
// sublists that contain the items in order. 
// You can then iterate through that list, subtract (last-first), and take 
// the item that has the smallest value. That will be the shortest sublist 
// that matches the criteria. 

Con algunos trabajos, esto podría hacerse más eficiente. Por ejemplo, si 'queryArray' contiene [1, 2, 3] y inputArray contiene [1, 7, 4, 9, 1, 3, 6, 4, 1, 8, 2, 3], el código anterior encontrará tres coincidencias (comenzando en las posiciones 0, 4 y 8). Un código ligeramente más inteligente podría determinar que cuando se encuentra el 1 en la posición 4, ya que no se encontró 2 antes, cualquier secuencia que comience en la primera posición sería más larga que la secuencia que comienza en la posición 4 y por lo tanto cortocircuitaría la primera secuencia y comenzar de nuevo en la nueva posición. Sin embargo, eso complica un poco el código.

Answer 2

El algoritmo:
Para cada elemento de la matriz de consulta, almacenar en un mapa M (V → (I, P)), V es el elemento, i es un índice dentro de la matriz de entrada, P es la posición en la matriz de consulta. (El índice en la matriz de entrada para algunos P es el más grande tal que la consulta [0..P] es una subsecuencia de la entrada [I..curr])

Iterate a través de la matriz.
Si el valor es el primer término en la matriz de consulta: Almacene el índice actual como I.
Else: almacena el valor del índice del elemento anterior en la matriz de consulta, p. M[currVal].I = M[query[M[currVal].P-1]].I.
Si el valor es el último término: compruebe si [I..curr] es un nuevo mejor.

Complejidad
La complejidad de este es O (N), donde N es el tamaño de la matriz de entrada.

N.B.
Este código espera que no se repitan elementos en la matriz de consulta. Para atender esto, podemos usar un mapa M (V → listOf ((I, P))). Esto es O (N hC (Q)), donde hC (Q) es el recuento del modo de la matriz de consulta.
Sería aún mejor utilizar M (V → listOf ((linkedList (I), P))). Cuando los elementos repetidos se producen consecutivamente en la matriz de consulta, utilizamos una lista vinculada. La actualización de esos valores se convierte en O (1). La complejidad es entonces O (N hC (D (Q))), donde D (Q) es Q con términos consecutivos fusionados.

Implementación
aplicación java muestra está disponible here. Esto no funciona para los elementos repetidos en la matriz de consulta, ni tampoco la comprobación de errores, etc.

Answer 3

No desea un HashSet sino un árbol o matriz (clasificado) como el valor en el diccionario; el diccionario contiene asignaciones de valores que se encuentran en la matriz de entrada a la lista (ordenada) de índices donde aparece ese valor.

A continuación, haga lo siguiente

• buscar la primera entrada de la consulta. Elija el índice más bajo donde aparece.
• Busque la segunda entrada; elige la entrada más baja mayor que el índice de la primera.
• Busque el tercero; elige el más bajo mayor que el segundo. (Etc.)
• Al llegar a la última entrada en la consulta, (1 + último índice - primer índice) es el tamaño de la coincidencia más pequeña.
• Ahora coge el segundo índice de la primera consulta, repetida, etc.
• Escoja el partido más pequeño encontrado de cualquiera de los índices de inicio.

(Tenga en cuenta que el "mayor de menor producción" es una operación suministrado con árboles ordenados, o se puede encontrar a través de la búsqueda binaria en un arreglo ordenado.)

La complejidad de este es de aproximadamente O(M*n*log n) donde M es la longitud de la consulta y n es el número promedio de índices en los que aparece un valor determinado en la matriz de entrada. Puede modificar la estrategia seleccionando ese valor de matriz de consulta que aparece con menos frecuencia para el punto de partida y subiendo y bajando desde allí; si hay k de esas entradas (k < = n), entonces la complejidad es O(M*k*log n).

Answer 4

Después que ha recibido todas las posiciones (indicadores) en el inputArray:

2 --> position {0,2} // note: I change them to 0-based array 
1 --> position {5,6} // I suppose it's {5,6} to make it more complex, in your code it's only {5} 
7 --> position {7} 

Puedo utilizar una recursividad para obtener todos los caminos posibles. [0-> 5-> 7] [0-> 6-> 7] [2-> 5-> 7] [2-> 6-> 7]. El total es 2 * 2 * 1 = 4 caminos posibles. Obviamente, quien tiene Min(Last-First) es la ruta más corta (ventana más pequeña), esos números en el medio de la ruta no importan. Aquí viene el código.

struct Pair 
{ 
    public int Number; // the number in queryArray 
    public int[] Indexes; // the positions of the number 
} 
static List<int[]> results = new List<int[]>(); //store all possible paths 
static Stack<int> currResult = new Stack<int>(); // the container of current path 
static int[] inputArray, queryArray; 
static Pair[] pairs; 

Después de las estructuras de datos, aquí está el Main.

inputArray = new int[] { 2, 7, 1, 5, 2, 8, 0, 1, 4, 7 }; //my test case 
queryArray = new int[] { 2, 1, 7 }; 
pairs = (from n in queryArray 
     select new Pair { Number = n, Indexes = inputArray.FindAllIndexes(i => i == n) }).ToArray(); 
Go(0); 

FindAllIndexes es un método de extensión para ayudar a encontrar todos los índices.

public static int[] FindAllIndexes<T>(this IEnumerable<T> source, Func<T,bool> predicate) 
{ 
    //do necessary check here, then 
    Queue<int> indexes = new Queue<int>(); 
    for (int i = 0;i<source.Count();i++) 
      if (predicate(source.ElementAt(i))) indexes.Enqueue(i); 
    return indexes.ToArray(); 
} 

El método de recursión:

static void Go(int depth) 
{ 
    if (depth == pairs.Length) 
    { 
     results.Add(currResult.Reverse().ToArray()); 
    } 
    else 
    { 
     var indexes = pairs[depth].Indexes; 
     for (int i = 0; i < indexes.Length; i++) 
     { 
      if (depth == 0 || indexes[i] > currResult.Last()) 
      { 
       currResult.Push(indexes[i]); 
       Go(depth + 1); 
       currResult.Pop(); 
      } 
     } 
    } 
} 

Por fin, un bucle de results puede encontrar el Min(Last-First) resultado (ventana más corta).

Answer 5

Algoritmo:

1. obtener todos los índices en el inputArray de todos queryArray valora
2. orden ellos ascendiendo por el índice
3. usando cada índice (x) como un punto de partida encontrar el primer índice más alto (y) de modo que el segmento inputArray [xy] contiene todos queryArray valores
4. mantener solo los segmentos que tienen el queryArray artículos con el fin
5. para los segmentos por sus longitudes, ascendentes

C# aplicación:

En primer lugar obtener todos los índices en el inputArray de todos los valores queryArray y el orden ascendente de ellos por el índice.

public static int[] SmallestWindow(int[] inputArray, int[] queryArray) 
{ 
    var indexed = queryArray 
     .SelectMany(x => inputArray 
          .Select((y, i) => new 
           { 
            Value = y, 
            Index = i 
           }) 
          .Where(y => y.Value == x)) 
     .OrderBy(x => x.Index) 
     .ToList(); 

A continuación, utilizando cada índice (x) como punto de partida encontrar la primera mayor índice (y) tal que el segmento inputArray [X-Y] contiene todos los valores queryArray.

var segments = indexed 
     .Select(x => 
      { 
       var unique = new HashSet<int>(); 
       return new 
        { 
         Item = x, 
         Followers = indexed 
          .Where(y => y.Index >= x.Index) 
          .TakeWhile(y => unique.Count != queryArray.Length) 
          .Select(y => 
           { 
            unique.Add(y.Value); 
            return y; 
           }) 
          .ToList(), 
         IsComplete = unique.Count == queryArray.Length 
        }; 
      }) 
     .Where(x => x.IsComplete); 

Ahora solo guarde los segmentos que tienen los elementos de la orden query en orden.

var queryIndexed = segments 
     .Select(x => x.Followers.Select(y => new 
      { 
       QIndex = Array.IndexOf(queryArray, y.Value), 
       y.Index, 
       y.Value 
      }).ToArray()); 

    var queryOrdered = queryIndexed 
     .Where(item => 
      { 
       var qindex = item.Select(x => x.QIndex).ToList(); 
       bool changed; 
       do 
       { 
        changed = false; 
        for (int i = 1; i < qindex.Count; i++) 
        { 
         if (qindex[i] <= qindex[i - 1]) 
         { 
          qindex.RemoveAt(i); 
          changed = true; 
         } 
        } 
       } while (changed); 
       return qindex.Count == queryArray.Length; 
      }); 

Finalmente, ordene los segmentos por su longitud, ascendente. El primer segmento en el resultado es la ventana más pequeña en inputArray que contiene todos los valores de queryArray en el orden de queryArray.

var result = queryOrdered 
     .Select(x => new[] 
      { 
       x.First().Index, 
       x.Last().Index 
      }) 
     .OrderBy(x => x[1] - x[0]); 

    var best = result.FirstOrDefault(); 
    return best; 
} 

prueba con salida

public void Test() 
{ 
    var inputArray = new[] { 2, 1, 5, 6, 8, 1, 8, 6, 2, 9, 2, 9, 1, 2 }; 
    var queryArray = new[] { 6, 1, 2 }; 

    var result = SmallestWindow(inputArray, queryArray); 

    if (result == null) 
    { 
     Console.WriteLine("no matching window"); 
    } 
    else 
    { 
     Console.WriteLine("Smallest window is indexes " + result[0] + " to " + result[1]); 
    } 
} 

:

Smallest window is indexes 3 to 8 

Answer 6

Gracias a todos por sus entradas. He cambiado un poco mi código y lo encuentro funcionando. Aunque puede que no sea muy eficiente pero me complace resolver usando mi cabeza :). Por favor, dar su regeneración

Aquí está mi clase Par de tener número y posición como variable de

public class Pair 
    { 
    public int Number; 
    public List<int> Position; 
    } 

Aquí es un método que devolverá la lista de todos los pares.

 public static Pair[] GetIndex(int[] inputArray, int[] query) 
     { 
     Pair[] pairList = new Pair[query.Length]; 
     int pairIndex = 0; 
     foreach (int i in query) 
     { 
      Pair pair = new Pair(); 
      int index = 0; 
      pair.Position = new List<int>(); 
      foreach (int j in inputArray) 
      {      
       if (i == j) 
       { 
        pair.Position.Add(index); 
       } 
       index++; 
      } 
      pair.Number = i; 
      pairList[pairIndex] = pair; 
      pairIndex++; 
     } 
     return pairList; 
    } 

Aquí es la línea de código en el método principal

 Pair[] pairs = NewCollection.GetIndex(array, intQuery); 

     List<int> minWindow = new List<int>(); 
     for (int i = 0; i <pairs.Length - 1; i++) 
     { 
      List<int> first = pairs[i].Position; 
      List<int> second = pairs[i + 1].Position; 
      int? temp = null; 
      int? temp1 = null; 
      foreach(int m in first) 
      { 
       foreach (int n in second) 
       { 
        if (n > m) 
        { 
         temp = m; 
         temp1 = n; 
        }       
       }      
      } 
      if (temp.HasValue && temp1.HasValue) 
      { 
       if (!minWindow.Contains((int)temp)) 
        minWindow.Add((int)temp); 
       if (!minWindow.Contains((int)temp1)) 
        minWindow.Add((int)temp1); 
      } 
      else 
      { 
       Console.WriteLine(" Bad Query array"); 
       minWindow.Clear(); 
       break;      
      } 
     } 

     if(minWindow.Count > 0) 
     { 
     Console.WriteLine("Minimum Window is :"); 
     foreach(int i in minWindow) 
     { 
      Console.WriteLine(i + " "); 
     } 
     } 

Answer 7

Vale la pena señalar que este problema está relacionado con el problema subsecuencia común más larga, por lo que viene con algoritmos que se ejecutan en el mejor de O (n^2) el tiempo en el caso general con duplicados sería un desafío.

Answer 8

Por si alguien está interesado en C++ con la ejecución O (n log (k))

void findMinWindow(const vector<int>& input, const vector<int>& query) { 
     map<int, int> qtree; 
     for(vector<int>::const_iterator itr=query.begin(); itr!=query.end(); itr++) { 
      qtree[*itr] = 0; 
     } 

     int first_ptr=0; 
     int begin_ptr=0; 

     int index1 = 0; 
     int queptr = 0; 

     int flip = 0; 

     while(true) { 
      //check if value is in query 
      if(qtree.find(input[index1]) != qtree.end()) { 
       int x = qtree[input[index1]]; 
       if(0 == x) { 
        flip++; 
       } 
       qtree[input[index1]] = ++x; 
       } 

       //remove all nodes that are not required and 
       //yet satisfy the all query condition. 
       while(query.size() == flip) { 
       //done nothing more 
       if(queptr == input.size()) { 
        break; 
       } 

       //check if queptr is pointing to node in the query 
       if(qtree.find(input[queptr]) != qtree.end()) { 
        int y = qtree[input[queptr]]; 
        //more nodes and the queue is pointing to deleteable node 
        //condense the nodes 
        if(y > 1) { 
        qtree[input[queptr]] = --y; 
        queptr++; 
        } else { 
        //cant condense more just keep that memory 
        if((!first_ptr && !begin_ptr) || 
         ((first_ptr-begin_ptr)>(index1-queptr))) { 
         first_ptr=index1; 
         begin_ptr=queptr; 
        } 
        break; 
        } 
       } else { 
        queptr++; 
       } 
       } 

      index1++; 

      if(index1==input.size()) { 
       break; 
      } 
     } 
     cout<<"["<<begin_ptr<<" - "<<first_ptr<<"]"<<endl; 
    } 

aquí la principal llamándolo.

#include <iostream> 
    #include <vector> 
    #include <map> 

    using namespace std; 

    int main() { 
     vector<int> input; 
     input.push_back(2); 
     input.push_back(5); 
     input.push_back(2); 
     input.push_back(8); 
     input.push_back(0); 
     input.push_back(1); 
     input.push_back(4); 
     input.push_back(7); 

     vector<int> query1; 
     query1.push_back(2); 
     query1.push_back(8); 
     query1.push_back(0); 

     vector<int> query2; 
     query2.push_back(2); 
     query2.push_back(1); 
     query2.push_back(7); 

     vector<int> query3; 
     query3.push_back(1); 
     query3.push_back(4); 

     findMinWindow(input, query1); 
     findMinWindow(input, query2); 
     findMinWindow(input, query3); 
    }