php - 如何对类似于链表的条目进行排序？

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
 */