secuencia frecuente de los números en una matriz

Question

matriz (3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 65, 4, 7, 13, 32)

la secuencia de números frecuentes será (3, 5) f=2 + (4, 7, 13) f=2

cualquier algoritmo o pseudo código para encontrar que?

actualización (1):

si (7, 13) también ocurrencia que se incluirá en el más largo de su frecuencia de actualización por lo

(4, 7, 13) f=3 y así sucesivamente ...

Update (2):

en caso de (1,2,3,4,1,2,3,4,1,2,7,8,7,8,3,4,3,4,1,2) la salida debe ser (1,2,3,4) & (3,4,1,2)

& (7,8), para que quede claro en cuenta cada número como una palabra y que desea encontrar frases más frecuentes

por lo que es común ver a una misma palabra (s) en un montón de frases pero si cualquier frase fue sub -string para cualquier otro

frase (s) no se debe considerar como una frase, pero se actualizará la frecuencia de las frases que incluye

Answer 1

** EDITAR **: ligeramente mejor de aplicación, ahora también devuelve frecuencias y tiene un mejor filtro de secuencia.

function getFrequences($input, $minimalSequenceSize = 2) { 
    $sequences = array(); 
    $frequences = array(); 

    $len = count($input); 
    for ($i=0; $i<$len; $i++) { 
     $offset = $i; 

     for ($j=$i+$minimalSequenceSize; $j<$len; $j++) { 
     if ($input[$offset] == $input[$j]) { 
      $sequenceSize = 1; 
      $sequence = array($input[$offset]); 
      while (($offset + $sequenceSize < $j) 
       && ($input[$offset+$sequenceSize] == $input[$j+$sequenceSize])) { 

       if (false !== ($seqIndex = array_search($sequence, $frequences))) { 
        // we already have this sequence, since we found a bigger one, remove the old one 
        array_splice($sequences, $seqIndex, 1); 
        array_splice($frequences, $seqIndex, 1); 
       }    

       $sequence[] = $input[$offset+$sequenceSize]; 
       $sequenceSize++; 
      } 

      if ($sequenceSize >= $minimalSequenceSize) { 
       if (false !== ($seqIndex = array_search($sequence, $sequences))) { 
        $frequences[$seqIndex]++; 
       } else { 
        $sequences[] = $sequence; 
        $frequences[] = 2; // we have two occurances already 
       } 
       // $i += $sequenceSize; // move $i so we don't reuse the same sub-sequence 
       break; 
      } 
     } 
     } 
    } 

    // remove sequences that are sub-sequence of another frequence 
    // ** comment this to keep all sequences regardless ** 
    $len = count($sequences); 
    for ($i=0; $i<$len; $i++) { 
     $freq_i = $sequences[$i]; 
     for ($j=$i+1; $j<$len; $j++) { 
     $freq_j = $sequences[$j]; 
     $freq_inter = array_intersect($freq_i, $freq_j); 
     if (count($freq_inter) != 0) { 
      $len--; 
      if (count($freq_i) > count($freq_j)) { 
       array_splice($sequences, $j, 1); 
       array_splice($frequences, $j, 1); 
       $j--; 
      } else { 
       array_splice($sequences, $i, 1); 
       array_splice($frequences, $i, 1); 
       $i--; 
       break; 
      } 
     } 
     } 
    } 

    return array($sequences, $frequences); 
}; 

caso de prueba

header('Content-type: text/plain'); 

$input = array(3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 3, 5, 65, 4, 7, 13, 32, 5, 48, 4, 7, 13); 

list($sequences, $frequences) = getFrequences($input); 
foreach ($sequences as $i => $s) { 
    echo "(" . implode(',', $s) . ') f=' . $frequences[$i] . "\n"; 
} 

** ** EDITAR: aquí está una actualización de la función. Fue casi completamente reescrito ... dime si esto es lo que estabas buscando. También agregué una verificación de redundancia para evitar contar la misma secuencia, o subsecuencia, dos veces.

function getFrequences2($input, $minSequenceSize = 2) { 
    $sequences = array(); 

    $last_offset = 0; 
    $last_offset_len = 0; 

    $len = count($input); 
    for ($i=0; $i<$len; $i++) { 
    for ($j=$i+$minSequenceSize; $j<$len; $j++) { 
     if ($input[$i] == $input[$j]) { 
      $offset = 1; 
      $sub = array($input[$i]); 
      while ($i + $offset < $j && $j + $offset < $len) { 
       if ($input[$i + $offset] == $input[$j + $offset]) { 
       array_push($sub, $input[$i + $offset]); 
       } else { 
       break; 
       } 
       $offset++; 
      } 

      $sub_len = count($sub); 
      if ($sub_len >= $minSequenceSize) { 
       // $sub must contain more elements than the last sequence found 
       // otherwise we will count the same sequence twice 
       if ($last_offset + $last_offset_len >= $i + $sub_len) { 
       // we already saw this sequence... ignore 
       continue; 
       } else { 
       // save offset and sub_len for future check 
       $last_offset = $i; 
       $last_offset_len = $sub_len; 
       } 

       foreach ($sequences as & $sequence) { 
       $sequence_len = count($sequence['values']); 
       if ($sequence_len == $sub_len && $sequence['values'] == $sub) { 
        //echo "Found add-full ".var_export($sub, true)." at $i and $j...\n"; 
        $sequence['frequence']++; 
        break 2; 
       } else { 
        if ($sequence_len > $sub_len) { 
         $end = $sequence_len - $sub_len; 
         $values = $sequence['values']; 
         $slice_len = $sub_len; 
         $test = $sub; 
        } else { 
         $end = $sub_len - $sequence_len; 
         $values = $sub; 
         $slice_len = $sequence_len; 
         $test = $sequence['values']; 
        } 
        for ($k=0; $k<=$end; $k++) { 
         if (array_slice($values, $k, $slice_len) == $test) { 
          //echo "Found add-part ".implode(',',$sub)." which is part of ".implode(',',$values)." at $i and $j...\n"; 
          $sequence['values'] = $values; 
          $sequence['frequence']++; 
          break 3; 
         } 
        } 
       } 
       } 

       //echo "Found new ".implode(',',$sub)." at $i and $j...\n"; 
       array_push($sequences, array('values' => $sub, 'frequence' => 2)); 
       break; 
      } 
     } 
    } 
    } 

    return $sequences; 
}; 

Answer 2

En python3

>>> from collections import Counter 
>>> count_hash=Counter() 
>>> T=(3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 65, 4, 7, 13, 32) 
>>> for i in range(2,len(T)+1): 
...  for j in range(len(T)+1-i): 
...   count_hash[T[j:j+i]]+=1 
... 
>>> for k,v in count_hash.items(): 
...  if v >= 2: 
...   print(k,v) 
... 
(3, 5) 2 
(4, 7, 13) 2 
(7, 13) 2 
(4, 7) 2 

¿Necesita filtrar (7,13) y (4,7)? ¿Qué sucede si también hubo (99, 7, 14) en la secuencia?

un Counter es lo mismo que un hash utilizado para realizar un seguimiento del número de veces que vemos cada subcadena
Los dos bucles for anidados producir todas las subcadenas de T, utilizando count_hash para acumular el recuento de cada subcadena.
El final para filtros de bucle todos esos subcadenas que sólo se produjo una vez

Aquí hay una versión con un filtro

from collections import Counter 
def substrings(t, minlen=2): 
    tlen = len(t) 
    return (t[j:j+i] for i in range(minlen, tlen+1) for j in range(tlen+1-i)) 

def get_freq(*t): 
    counter = Counter(substrings(t)) 
    for k in sorted(counter, key=len): 
     v=counter[k] 
     if v < 2: 
      del counter[k] 
      continue 
     for t in substrings(k): 
      if t in counter: 
       if t==k: 
        continue 
       counter[k]+=counter[t]-v 
       del counter[t] 
    return counter 

print(get_freq(3, 5, 1, 3, 5, 48, 4, 7, 13, 55, 65, 4, 7, 13, 32, 4, 7)) 
print(get_freq(1,2,3,4,1,2,3,4,1,2,7,8,7,8,3,4,3,4,1,2)) 

la salida es

Counter({(4, 7, 13): 3, (3, 5): 2}) 
Counter({(1, 2, 3, 4, 1, 2): 8, (7, 8): 2}) # Is this the right answer? 

que es por lo pregunté cómo el filtrado debería funcionar para la secuencia que di en los comentarios

Answer 3

Ok, solo para comenzar la discusión.

1. Cree otra matriz/mapa, llame a esta matriz de pesaje .
2. Comience a iterar en la matriz de valores.
3. Para cada valor en valores matriz, incremente la posición correspondiente en weightage matriz. Ejemplo: para 3 aumentos weightage [3] ++, para 48 weightage [48] ++.
4. Después de la iteración la matriz de coeficiente de ponderación contiene repeticiones