연결된 목록과 비슷한 항목을 정렬하는 방법?

Question

나는 다음과 같은 데이터 구조를 가지고 있으며 이것을 before과 after 값을 기준으로 정렬하고 싶습니다.

array (size=5) 
    0 => 
    array (size=3) 
     'id' => int 14 
     'parentId' => int 0 
     'before' => int 15 
    1 => 
    array (size=3) 
     'id' => int 15 
     'parentId' => int 0 
     'after' => int 14 
    2 => 
    array (size=3) 
     'id' => int 9 
     'parentId' => int 0 
     'after' => int 15 
    3 => 
    array (size=3) 
     'id' => int 8 
     'parentId' => int 0 
     'after' => int 9 
    4 => 
    array (size=3) 
     'id' => int 1 
     'parentId' => int 0 
     'after' => int 14 

PHP로 이것을 수행 할 수있는 좋은 방법이 있습니까?

Answer 1

직접적인 "한 줄짜리"유형의 해결책이 없다고 생각합니다.

parentId이 분류에 어떤 의미가 있는지 확실하지 않지만, 그렇지 않은 경우 this question about sorting an array of Javascript includes by dependency과 매우 흡사합니다. 이번 주 초에 대답했습니다.

유일한 차이점은 종속성을 기준으로 정렬하기 전에 해당 "이전"항목을 해당 행의 "이후"항목으로 변환해야한다는 것입니다.

$data = [ 
    ["id" => 14, "parentId" => 0, "before" => 15], 
    ["id" => 15, "parentId" => 0, "after" => 14], 
    ["id" => 9, "parentId" => 0, "after" => 15], 
    ["id" => 8, "parentId" => 0, "after" => 9], 
    ["id" => 1, "parentId" => 0, "after" => 14] 
]; 

// Use the ID of each element as the array index. 
$data = array_combine(array_column($data, "id"), $data); 
// Convert each "after" entry into an array. 
$data = array_map(function($element) { 
     $element["after"] = isset($element["after"]) ? [$element["after"]] : []; 
     return $element; 
    }, $data); 
// Convert each "before" entry into an "after" entry. 
foreach ($data as $id => $element) { 
    if (isset($element["before"])) { 
     $data[$element["before"]]["after"][] = $id; 
     unset($data[$id]["before"]); 
    } 
} 
// Remove empty "after" entries. 
$data = array_map(function($element) { 
     if (!count($element["after"])) { 
      unset($element["after"]); 
     } 
     return $element; 
    }, $data); 

$sorted = []; 
while ($count = count($data)) { 
    // Remove any met dependencies. 
    foreach ($data as $id => $element) { 
     if (isset($element["after"])) { 
      foreach ($element["after"] as $after_id => $after_element) { 
       if (isset($sorted[$after_element])) { 
        unset($data[$id]["after"][$after_id]); 
       } 
      } 
      if (!count($data[$id]["after"])) { 
       unset($data[$id]["after"]); 
      } 
     } 
    } 
    // Add elements with no more dependencies to the output array. 
    foreach ($data as $id => $element) { 
     if (!isset($element["after"])) { 
      $sorted[$id] = $element; 
      unset($data[$id]); 
     } 
    } 
    if (count($data) == $count) { 
     die("Unresolvable dependency"); 
    } 
} 
var_dump($sorted); 
/* 
array (size=5) 
    14 => 
    array (size=2) 
     'id' => int 14 
     'parentId' => int 0 
    15 => 
    array (size=2) 
     'id' => int 15 
     'parentId' => int 0 
    1 => 
    array (size=2) 
     'id' => int 1 
     'parentId' => int 0 
    9 => 
    array (size=2) 
     'id' => int 9 
     'parentId' => int 0 
    8 => 
    array (size=2) 
     'id' => int 8 
     'parentId' => int 0 
*/ 

Answer 2

사용자의 필요에 따라 uasort() 기능을 사용할 수 있다고 생각합니다. 이 비교 함수를 정의하려면, 나는 before 조건에 모두 after 조건을 변환하는 제안 :

$array = [ 
    [ 
     'id'  => 14, 
     'parentId' => 0, 
     'before' => 15 
    ], 
    [ 
     'id'  => 15, 
     'parentId' => 0, 
     'after' => 14 
    ], 
    [ 
     'id'  => 9, 
     'parentId' => 0, 
     'after' => 15 
    ], 
    [ 
     'id'  => 8, 
     'parentId' => 0, 
     'after' => 9 
    ], 

    [ 
     'id'  => 1, 
     'parentId' => 0, 
     'after' => 14 
    ] 
]; 

//transform all after conditions to before conditions 
function defineBeforeCondition($array) 
{ 
    $befores = array_column($array, 'before', 'id'); 
    $afters = array_column($array, 'after', 'id'); 
    return array_merge(array_chunk($befores, 1, true), array_map('array_flip', array_chunk($afters, 1, true))); 
} 

$condition = defineBeforeCondition($array); 

지금 당신은 당신의 비교 함수에 $condition을 사용할 수

$compare = function ($array1, $array2) use ($condition) 
{ 
    //iterate through before conditions 
    foreach ($condition as $before) { 
     //if there is a match 
     if (isset($before[$array1['id']]) && $before[$array1['id']] === $array2['id']) { 
      //if the value of the first element is greater than the value of the second element, 
      //but the first element should precede the second, return -1 
      if ($array1['id'] > $array2['id']) { 
       return -1; 
      } 
      //otherwise make a normal comparison 
      //note the spaceship operator for PHP >= 7.0 
      return $array1['id'] <=> $array2['id']; 
     } 
    } 
    //no data, move down the first element 
    return 1; 
}; 

uasort($array, $compare); 
var_dump($array); 

array (size=5) 
    0 => 
    array (size=3) 
     'id' => int 14 
     'parentId' => int 0 
     'before' => int 15 
    4 => 
    array (size=3) 
     'id' => int 1 
     'parentId' => int 0 
     'after' => int 14 
    1 => 
    array (size=3) 
     'id' => int 15 
     'parentId' => int 0 
     'after' => int 14 
    2 => 
    array (size=3) 
     'id' => int 9 
     'parentId' => int 0 
     'after' => int 15 
    3 => 
    array (size=3) 
     'id' => int 8 
     'parentId' => int 0 
     'after' => int 9