Tetris-ción de una matriz

Question

Considerar la siguiente matriz:

/www/htdocs/1/sites/lib/abcdedd 
/www/htdocs/1/sites/conf/xyz 
/www/htdocs/1/sites/conf/abc/def 
/www/htdocs/1/sites/htdocs/xyz 
/www/htdocs/1/sites/lib2/abcdedd 

¿cuál es el camino más corto y más elegante de la detección de la ruta base común - en este caso

/www/htdocs/1/sites/ 

y eliminarlo de todos los elementos en la matriz?

lib/abcdedd 
conf/xyz 
conf/abc/def 
htdocs/xyz 
lib2/abcdedd 

Answer 1

$common = PHP_INT_MAX; 
foreach ($a as $item) { 
     $common = min($common, str_common($a[0], $item, $common)); 
} 

$result = array(); 
foreach ($a as $item) { 
     $result[] = substr($item, $common); 
} 
print_r($result); 

function str_common($a, $b, $max) 
{ 
     $pos = 0; 
     $last_slash = 0; 
     $len = min(strlen($a), strlen($b), $max + 1); 
     while ($pos < $len) { 
       if ($a{$pos} != $b{$pos}) return $last_slash; 
       if ($a{$pos} == '/') $last_slash = $pos; 
       $pos++; 
     } 
     return $last_slash; 
} 

Answer 2

a cargar en una estructura de datos trie. Comenzando desde el nodo padre, vea cuál está teniendo un conteo de niños mayor que uno. Una vez que encuentre ese nodo mágico, simplemente desmantele la estructura del nodo padre y tenga el nodo actual como raíz.

Answer 3

Quiero explode valores basados ​​en/y luego uso array_intersect_assoc para detectar los elementos comunes y asegurar que tengan el índice correspondiente correcto en la matriz. La matriz resultante podría recombinarse para producir la ruta común.

function getCommonPath($pathArray) 
{ 
    $pathElements = array(); 

    foreach($pathArray as $path) 
    { 
     $pathElements[] = explode("/",$path); 
    } 

    $commonPath = $pathElements[0]; 

    for($i=1;$i<count($pathElements);$i++) 
    { 
     $commonPath = array_intersect_assoc($commonPath,$pathElements[$i]); 
    } 

    if(is_array($commonPath) return implode("/",$commonPath); 
    else return null; 
} 

function removeCommonPath($pathArray) 
{ 
    $commonPath = getCommonPath($pathArray()); 

    for($i=0;$i<count($pathArray);$i++) 
    { 
     $pathArray[$i] = substr($pathArray[$i],str_len($commonPath)); 
    } 

    return $pathArray; 
} 

Esto no se ha probado, pero, la idea es que la matriz $commonPath solamente siempre contiene los elementos de la trayectoria que han sido contenida en todas las matrices de ruta que han sido comparados contra ella. Cuando el bucle se haya completado, simplemente recombinarlo con/para obtener el verdadero $commonPath

actualización Como ha señalado Félix Kling, array_intersect no considerará caminos que tienen elementos comunes, pero en diferente orden ... Para solucionar esto, he utilizado en lugar de array_intersect_assocarray_intersect

actualización código Agregado para eliminar la ruta común (o Tetris it!) de la matriz también.

Answer 4

Un enfoque ingenuo sería explotar las rutas en el / y sucesivamente comparar cada elemento en las matrices. Por ejemplo, el primer elemento estaría vacío en todas las matrices, por lo que se eliminará, el siguiente elemento será www, es el mismo en todas las matrices, por lo que se elimina, etc.

Algo así como (no probado)

$exploded_paths = array(); 

foreach($paths as $path) { 
    $exploded_paths[] = explode('/', $path); 
} 

$equal = true; 
$ref = &$exploded_paths[0]; // compare against the first path for simplicity 

while($equal) { 
    foreach($exploded_paths as $path_parts) { 
     if($path_parts[0] !== $ref[0]) { 
      $equal = false; 
      break; 
     } 
    } 
    if($equal) { 
     foreach($exploded_paths as &$path_parts) { 
      array_shift($path_parts); // remove the first element 
     } 
    } 
} 

Después sólo hay que implosionar los elementos en $exploded_paths nuevo:

function impl($arr) { 
    return '/' . implode('/', $arr); 
} 
$paths = array_map('impl', $exploded_paths); 

que me da:

Array 
(
    [0] => /lib/abcdedd 
    [1] => /conf/xyz 
    [2] => /conf/abc/def 
    [3] => /htdocs/xyz 
    [4] => /conf/xyz 
) 

Esto podría no escala bien,)

Answer 5

$values = array('/www/htdocs/1/sites/lib/abcdedd', 
       '/www/htdocs/1/sites/conf/xyz', 
       '/www/htdocs/1/sites/conf/abc/def', 
       '/www/htdocs/1/sites/htdocs/xyz', 
       '/www/htdocs/1/sites/lib2/abcdedd' 
); 


function splitArrayValues($r) { 
    return explode('/',$r); 
} 

function stripCommon($values) { 
    $testValues = array_map('splitArrayValues',$values); 

    $i = 0; 
    foreach($testValues[0] as $key => $value) { 
     foreach($testValues as $arraySetValues) { 
      if ($arraySetValues[$key] != $value) break 2; 
     } 
     $i++; 
    } 

    $returnArray = array(); 
    foreach($testValues as $value) { 
     $returnArray[] = implode('/',array_slice($value,$i)); 
    } 

    return $returnArray; 
} 


$newValues = stripCommon($values); 

echo '<pre>'; 
var_dump($newValues); 
echo '</pre>'; 

EDITAR variante de mi método original utilizando un array_walk para reconstruir la matriz

$values = array('/www/htdocs/1/sites/lib/abcdedd', 
       '/www/htdocs/1/sites/conf/xyz', 
       '/www/htdocs/1/sites/conf/abc/def', 
       '/www/htdocs/1/sites/htdocs/xyz', 
       '/www/htdocs/1/sites/lib2/abcdedd' 
); 


function splitArrayValues($r) { 
    return explode('/',$r); 
} 

function rejoinArrayValues(&$r,$d,$i) { 
    $r = implode('/',array_slice($r,$i)); 
} 

function stripCommon($values) { 
    $testValues = array_map('splitArrayValues',$values); 

    $i = 0; 
    foreach($testValues[0] as $key => $value) { 
     foreach($testValues as $arraySetValues) { 
      if ($arraySetValues[$key] != $value) break 2; 
     } 
     $i++; 
    } 

    array_walk($testValues, 'rejoinArrayValues', $i); 

    return $testValues; 
} 


$newValues = stripCommon($values); 

echo '<pre>'; 
var_dump($newValues); 
echo '</pre>'; 

EDITAR

La respuesta más eficiente y elegante es probable que implique tomar funciones y métodos de cada una de las respuestas proporcionadas

Answer 6

Esto tiene la ventaja de no tener complejidad de tiempo lineal; sin embargo, para la mayoría de los casos, el género definitivamente no será la operación que tome más tiempo.

Básicamente, la parte inteligente (al menos no pude encontrar un fallo) es que después de la clasificación solo tendrá que comparar la primera ruta con la última.

sort($a); 
$a = array_map(function ($el) { return explode("/", $el); }, $a); 
$first = reset($a); 
$last = end($a); 
for ($eqdepth = 0; $first[$eqdepth] === $last[$eqdepth]; $eqdepth++) {} 
array_walk($a, 
    function (&$el) use ($eqdepth) { 
     for ($i = 0; $i < $eqdepth; $i++) { 
      array_shift($el); 
     } 
    }); 
$res = array_map(function ($el) { return implode("/", $el); }, $a); 

Answer 7

escribir una función longest_common_prefix que toma dos cadenas como entrada. Luego, aplíquelo a las cuerdas en cualquier orden para reducirlas a su prefijo común. Como es asociativo y conmutativo, el orden no importa para el resultado.

Esto es lo mismo que para otras operaciones binarias como, por ejemplo, suma o máximo divisor común.

Answer 8

$arrMain = array(
      '/www/htdocs/1/sites/lib/abcdedd', 
      '/www/htdocs/1/sites/conf/xyz', 
      '/www/htdocs/1/sites/conf/abc/def', 
      '/www/htdocs/1/sites/htdocs/xyz', 
      '/www/htdocs/1/sites/lib2/abcdedd' 
); 
function explodePath($strPath){ 
    return explode("/", $strPath); 
} 

function removePath($strPath) 
{ 
    global $strCommon; 
    return str_replace($strCommon, '', $strPath); 
} 
$arrExplodedPaths = array_map('explodePath', $arrMain) ; 

//Check for common and skip first 1 
$strCommon = ''; 
for($i=1; $i< count($arrExplodedPaths[0]); $i++) 
{ 
    for($j = 0; $j < count($arrExplodedPaths); $j++) 
    { 
     if($arrExplodedPaths[0][ $i ] !== $arrExplodedPaths[ $j ][ $i ]) 
     { 
      break 2; 
     } 
    } 
    $strCommon .= '/'.$arrExplodedPaths[0][$i]; 
} 
print_r(array_map('removePath', $arrMain)); 

Esto funciona bien ... similar a marcar panadero, pero utiliza str_replace

Answer 9

Ok, no estoy seguro de que esto es a prueba de balas, pero creo que funciona:

echo array_reduce($array, function($reducedValue, $arrayValue) { 
    if($reducedValue === NULL) return $arrayValue; 
    for($i = 0; $i < strlen($reducedValue); $i++) { 
     if(!isset($arrayValue[$i]) || $arrayValue[$i] !== $reducedValue[$i]) { 
      return substr($reducedValue, 0, $i); 
     } 
    } 
    return $reducedValue; 
}); 

Esto tomará el primer valor en la matriz como cadena de referencia. Luego iterará sobre la cadena de referencia y comparará cada char con el carácter de la segunda cuerda en la misma posición. Si un char no concuerda, la cadena de referencia se acortará a la posición del char y se comparará la siguiente cuerda. La función devolverá la cadena de coincidencia más corta a continuación.

El rendimiento depende de las cadenas dadas. Cuanto antes se acorte la cadena de referencia, más rápido terminará el código. Sin embargo, realmente no tengo ni idea de cómo poner eso en una fórmula.

Encontré que el enfoque de Artefacto para ordenar las cadenas aumenta el rendimiento. Añadiendo

asort($array); 
$array = array(array_shift($array), array_pop($array)); 

antes de la array_reduce aumentará significativamente el rendimiento.

También tenga en cuenta que esto devolverá la subcadena más larga a juego inicial , que es más versátil, pero no le dará el camino común . Debe ejecutar

substr($result, 0, strrpos($result, '/')); 

en el resultado. Y a continuación, puede utilizar el resultado para eliminar los valores

print_r(array_map(function($v) use ($path){ 
    return str_replace($path, '', $v); 
}, $array)); 

que debe dar:

[0] => /lib/abcdedd 
[1] => /conf/xyz/ 
[2] => /conf/abc/def 
[3] => /htdocs/xyz 
[4] => /lib2/abcdedd 

Evaluación de bienvenida.

Answer 10

El problema se puede simplificar si solo se ve desde el ángulo de comparación de cadenas. Esto es probablemente más rápido que la división de matrices:

$longest = $tetris[0]; # or array_pop() 
foreach ($tetris as $cmp) { 
     while (strncmp($longest+"/", $cmp, strlen($longest)+1) !== 0) { 
       $longest = substr($longest, 0, strrpos($longest, "/")); 
     } 
} 

Answer 11

Probablemente demasiado ingenuo y no funciona pero funciona. He utilizado this algorithm:

<?php 

function strlcs($str1, $str2){ 
    $str1Len = strlen($str1); 
    $str2Len = strlen($str2); 
    $ret = array(); 

    if($str1Len == 0 || $str2Len == 0) 
     return $ret; //no similarities 

    $CSL = array(); //Common Sequence Length array 
    $intLargestSize = 0; 

    //initialize the CSL array to assume there are no similarities 
    for($i=0; $i<$str1Len; $i++){ 
     $CSL[$i] = array(); 
     for($j=0; $j<$str2Len; $j++){ 
      $CSL[$i][$j] = 0; 
     } 
    } 

    for($i=0; $i<$str1Len; $i++){ 
     for($j=0; $j<$str2Len; $j++){ 
      //check every combination of characters 
      if($str1[$i] == $str2[$j]){ 
       //these are the same in both strings 
       if($i == 0 || $j == 0) 
        //it's the first character, so it's clearly only 1 character long 
        $CSL[$i][$j] = 1; 
       else 
        //it's one character longer than the string from the previous character 
        $CSL[$i][$j] = $CSL[$i-1][$j-1] + 1; 

       if($CSL[$i][$j] > $intLargestSize){ 
        //remember this as the largest 
        $intLargestSize = $CSL[$i][$j]; 
        //wipe any previous results 
        $ret = array(); 
        //and then fall through to remember this new value 
       } 
       if($CSL[$i][$j] == $intLargestSize) 
        //remember the largest string(s) 
        $ret[] = substr($str1, $i-$intLargestSize+1, $intLargestSize); 
      } 
      //else, $CSL should be set to 0, which it was already initialized to 
     } 
    } 
    //return the list of matches 
    return $ret; 
} 


$arr = array(
'/www/htdocs/1/sites/lib/abcdedd', 
'/www/htdocs/1/sites/conf/xyz', 
'/www/htdocs/1/sites/conf/abc/def', 
'/www/htdocs/1/sites/htdocs/xyz', 
'/www/htdocs/1/sites/lib2/abcdedd' 
); 

// find the common substring 
$longestCommonSubstring = strlcs($arr[0], $arr[1]); 

// remvoe the common substring 
foreach ($arr as $k => $v) { 
    $arr[$k] = str_replace($longestCommonSubstring[0], '', $v); 
} 
var_dump($arr); 

Salida:

array(5) { 
    [0]=> 
    string(11) "lib/abcdedd" 
    [1]=> 
    string(8) "conf/xyz" 
    [2]=> 
    string(12) "conf/abc/def" 
    [3]=> 
    string(10) "htdocs/xyz" 
    [4]=> 
    string(12) "lib2/abcdedd" 
} 

:)

Answer 12

Tal vez portar el algoritmo os.path.commonprefix(m) usos de Python trabajarían?

def commonprefix(m): 
    "Given a list of pathnames, returns the longest common leading component" 
    if not m: return '' 
    s1 = min(m) 
    s2 = max(m) 
    n = min(len(s1), len(s2)) 
    for i in xrange(n): 
     if s1[i] != s2[i]: 
      return s1[:i] 
    return s1[:n] 

Eso es, uh ... algo así como

function commonprefix($m) { 
    if(!$m) return ""; 
    $s1 = min($m); 
    $s2 = max($m); 
    $n = min(strlen($s1), strlen($s2)); 
    for($i=0;$i<$n;$i++) if($s1[$i] != $s2[$i]) return substr($s1, 0, $i); 
    return substr($s1, 0, $n); 
} 

Después de eso sólo puede SUBSTR cada elemento de la lista original con la longitud del prefijo común como el desplazamiento inicial.

Answer 13

Se podría eliminar el prefijo de la manera más rápida, lectura de cada carácter sólo una vez:

function findLongestWord($lines, $delim = "/") 
{ 
    $max = 0; 
    $len = strlen($lines[0]); 

    // read first string once 
    for($i = 0; $i < $len; $i++) { 
     for($n = 1; $n < count($lines); $n++) { 
      if($lines[0][$i] != $lines[$n][$i]) { 
       // we've found a difference between current token 
       // stop search: 
       return $max; 
      } 
     } 
     if($lines[0][$i] == $delim) { 
      // we've found a complete token: 
      $max = $i + 1; 
     } 
    } 
    return $max; 
} 

$max = findLongestWord($lines); 
// cut prefix of len "max" 
for($n = 0; $n < count($lines); $n++) { 
    $lines[$n] = substr(lines[$n], $max, $len); 
} 

Answer 14

voy a tirar mi sombrero en el anillo ...

function longestCommonPrefix($a, $b) { 
    $i = 0; 
    $end = min(strlen($a), strlen($b)); 
    while ($i < $end && $a[$i] == $b[$i]) $i++; 
    return substr($a, 0, $i); 
} 

function longestCommonPrefixFromArray(array $strings) { 
    $count = count($strings); 
    if (!$count) return ''; 
    $prefix = reset($strings); 
    for ($i = 1; $i < $count; $i++) 
     $prefix = longestCommonPrefix($prefix, $strings[$i]); 
    return $prefix; 
} 

function stripPrefix(&$string, $foo, $length) { 
    $string = substr($string, $length); 
} 

Uso:

$paths = array(
    '/www/htdocs/1/sites/lib/abcdedd', 
    '/www/htdocs/1/sites/conf/xyz', 
    '/www/htdocs/1/sites/conf/abc/def', 
    '/www/htdocs/1/sites/htdocs/xyz', 
    '/www/htdocs/1/sites/lib2/abcdedd', 
); 

$longComPref = longestCommonPrefixFromArray($paths); 
array_walk($paths, 'stripPrefix', strlen($longComPref)); 
print_r($paths); 

Answer 15

Bueno, ya hay algunas soluciones aquí, pero solo porque fue divertido:

$values = array(
    '/www/htdocs/1/sites/lib/abcdedd', 
    '/www/htdocs/1/sites/conf/xyz', 
    '/www/htdocs/1/sites/conf/abc/def', 
    '/www/htdocs/1/sites/htdocs/xyz', 
    '/www/htdocs/1/sites/lib2/abcdedd' 
); 

function findCommon($values){ 
    $common = false; 
    foreach($values as &$p){ 
     $p = explode('/', $p); 
     if(!$common){ 
      $common = $p; 
     } else { 
      $common = array_intersect_assoc($common, $p); 
     } 
    } 
    return $common; 
} 
function removeCommon($values, $common){ 
    foreach($values as &$p){ 
     $p = explode('/', $p); 
     $p = array_diff_assoc($p, $common); 
     $p = implode('/', $p); 
    } 

    return $values; 
} 

echo '<pre>'; 
print_r(removeCommon($values, findCommon($values))); 
echo '</pre>'; 

Salida:

Array 
(
    [0] => lib/abcdedd 
    [1] => conf/xyz 
    [2] => conf/abc/def 
    [3] => htdocs/xyz 
    [4] => lib2/abcdedd 
) 

Answer 16

Bueno, teniendo en cuenta que se puede utilizar XOR en esta situación para encontrar las partes comunes de la cadena. Cada vez que tienes xor dos bytes iguales, obtienes un nullbyte como salida. Así que podemos utilizar eso para nuestra ventaja:

$first = $array[0]; 
$length = strlen($first); 
$count = count($array); 
for ($i = 1; $i < $count; $i++) { 
    $length = min($length, strspn($array[$i]^$first, chr(0))); 
} 

Después de eso solo bucle, la variable $length será igual a la basepart común más larga entre la matriz de cadenas.Entonces, podemos extraer la parte común del primer elemento:

$common = substr($array[0], 0, $length); 

Y ahí lo tiene. En función:

function commonPrefix(array $strings) { 
    $first = $strings[0]; 
    $length = strlen($first); 
    $count = count($strings); 
    for ($i = 1; $i < $count; $i++) { 
     $length = min($length, strspn($strings[$i]^$first, chr(0))); 
    } 
    return substr($first, 0, $length); 
} 

Nota que no utilice más de una iteración, pero esas iteraciones se realizan en las bibliotecas, por lo que en lenguajes interpretados esto tendrá un enorme aumento de la eficiencia ...

Ahora, si solo desea rutas completas, debemos truncar hasta el último carácter /. Por lo tanto:

$prefix = preg_replace('#/[^/]*$', '', commonPrefix($paths)); 

Ahora, que podría recortar excesivamente dos cadenas como /foo/bar y /foo/bar/baz serán cortadas a /foo. Pero por debajo de la adición de otra iteración ronda para determinar si el siguiente carácter es bien /o de final de cadena, no puede ver una forma de evitar eso ...