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

发布时间：2020-12-13 22:26:29 所属栏目：PHP教程来源：网络整理

导读：我有以下数据结构,我想根据前后值对其进行排序. 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 'parentI

我有以下数据结构,我想根据前后值对其进行排序.

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做到这一点？

解决方法

我认为没有直接的“单线”型解决方案.

我不清楚parentId是否对排序有任何意义,但如果没有,这与我本周早些时候回答的this question about sorting an array of Javascript includes by dependency非常相似.

唯一真正的区别是,在按依赖关系排序之前,您需要将这些“之前”条目转换为相应行上的“之后”条目.

$data = [
    ["id" => 14,"parentId" => 0,"before" => 15],["id" => 15,"after" => 14],["id" => 9,"after" => 15],["id" => 8,"after" => 9],["id" => 1,"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
 */

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!