어레이의 테트리스 설정

어레이의 테트리스 설정

다음 어레이를 고려합니다.

/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

공통 베이스 패스를 검출하는 가장 짧고 우아한 방법 - 이 경우

/www/htdocs/1/sites/

어레이 내의 모든 요소에서 삭제할 수 있습니까?

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

를 쓰다longest_common_prefix이치노다음으로 문자열에 임의의 순서로 적용하여 공통 프레픽스로 줄입니다.연관성과 가환성이 있기 때문에 순서는 결과에 상관없습니다.

이는 덧셈이나 최대공약수와 같은 다른 이진 연산과 동일합니다.

trie 데이터 구조에 로드합니다.부모 노드부터 시작하여 자녀 수가 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;
}

, 그럼 쓸 수 걸 요.XOR이 경우 문자열의 공통 부분을 찾습니다. 경우 가 생성됩니다.x " " 2 " " " " " " " " " . "이를 통해 다음과 같은 이점을 얻을 수 있습니다.

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

루프 에, 「」는$length 사이의 가장 긴.그런 다음 첫 번째 요소에서 공통 부분을 추출할 수 있습니다.

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

그게 다야.기능으로서:

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);
}

여러 번 반복을 사용하지만 이러한 반복은 라이브러리에서 수행되므로 인터프리터 언어에서는 효율성이 크게 향상됩니다.

이제./: 。그래서:

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

이제 너무 도 있어요. 예를 , 너무 수도 있어요./foo/bar ★★★★★★★★★★★★★★★★★」/foo/bar/baz로 will로 /foo그러나 다음 문자가 다음 문자 중 하나인지 확인하기 위해 다른 반복 라운드를 추가하는 것은 부족합니다./ 현악기 말단이라든가, 어떻게 해야 할지...

입니다./어레이의 모든 요소를 연속적으로 비교합니다.첫 배열에서 되고 다음 는 "예"가 .www모든 어레이에서 동일하기 때문에 삭제 등입니다.

(미검증) 같은 것

$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
        }
    }
}

에는 그 안에 있는 .$exploded_paths 추가:

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

그 결과 다음과 같이 됩니다.

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

이것은 잘 확장되지 않을 수 있습니다;)

좋아, 이게 방탄인지는 모르겠지만 효과가 있는 것 같아

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;
});

그러면 어레이의 첫 번째 값이 참조 문자열로 사용됩니다.그런 다음 참조 문자열에서 반복하여 각 문자를 같은 위치에 있는 두 번째 문자열의 문자와 비교합니다.문자가 일치하지 않으면 참조 문자열이 문자 위치로 단축되고 다음 문자열이 비교됩니다.그러면 함수는 가장 짧은 일치 문자열을 반환합니다.

성능은 주어진 문자열에 따라 달라집니다.참조 문자열이 짧을수록 코드는 더 빨리 종료됩니다.공식에 어떻게 넣어야 할지 모르겠어요.

나는 Artefacto의 현악기 정렬 방식이 성능을 향상시킨다는 것을 알았다.추가 중

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

before array_reduce이치노

또한 가장 긴 일치 첫 번째 서브스트링이 반환됩니다.이 서브스트링은 범용성이 높지만 공통 경로를 제공하지 않습니다.뛰어가야 해

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

결과에 따라.그런 다음 결과를 사용하여 값을 제거할 수 있습니다.

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

그 결과 다음과 같이 됩니다.

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

피드백을 환영합니다.

각 문자를 한 번만 읽고 가장 빠른 방법으로 접두사를 제거할 수 있습니다.

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);
}

이는 선형적인 시간 복잡성을 가지지 않는다는 장점이 있지만, 대부분의 경우 이러한 종류의 작업은 시간이 더 걸리지 않습니다.

기본적으로 여기서 좋은 점은(적어도 결함을 찾을 수 없었다) 정렬 후에는 첫 번째 경로와 마지막 경로만 비교하면 된다는 것입니다.

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);

$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>';

편집 array_walk를 사용하여 어레이를 재구축하는 기존 방식의 변형

$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>';

편집

가장 효율적이고 우아한 답변은 제공된 답변 각각에서 기능과 방법을 취하는 것입니다.

i i i i i i i 。explode한값, 으로 /snd//syslog를 사용합니다.array_intersect_assoc공통 요소를 감지하고 배열에 올바른 인덱스가 있는지 확인합니다.결과 배열을 재결합하여 공통 경로를 생성할 수 있습니다.

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;
}

아직 되지 않았지만, 그 은 '이것'입니다.$commonPath만 포함합니다.array 、 에에 、 에 array에 、 에 array array array 。되면 /로한 /로 재결합할 수 .$commonPath

업데이트 펠릭스 클링의 지적대로array_intersect공통 요소가 있지만 순서가 다른 경로는 고려하지 않습니다.이 문제를 해결하기 위해array_intersect_assoc대신array_intersect

공통 경로(또는 테트리스!)를 어레이에서 제거하기 위해 코드가 추가되었습니다.

문자열 비교 각도에서 보는 것만으로 문제를 단순화할 수 있습니다.이는 어레이 분할보다 빠를 수 있습니다.

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

아마도 Python의 알고리즘을 이식할 것이다.os.path.commonprefix(m)사용할 수 있을까요?

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]

그건, 어...비슷한 것

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);
}

그 후, 원래의 리스트의 각 요소를, 공통의 프리픽스의 길이를 개시 오프셋으로서 서브 스크랩 할 수 있습니다.

저는 출사표를 던질 거예요…

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);
}

사용방법:

$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);

여기에는 이미 몇 가지 해결책이 있지만, 단지 재미있었기 때문에:

$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>';

출력:

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

$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 ) );

이거 잘 작동하는데...마크 베이커와 비슷하지만 str_replace를 사용합니다.

아마도 너무 순진하고 순진하지만 효과가 있다.이 알고리즘을 사용하고 있습니다.

<?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);

출력:

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"
}

:)

언급URL : https://stackoverflow.com/questions/3275258/tetris-ing-an-array