단일 차원 배열에서 데이터를 사용하여 알고리즘으로 다차원 배열 생성

Question

단일 차원의 PHP 객체 배열이 있습니다. 각 객체에는 두 가지 속성이 있습니다. 하나의 속성은 객체의 고유 ID이고 다른 속성은 배열의 다른 객체의 고유 ID입니다. 예를 들어:

array(3) {
  [0]=>
  object(stdClass)#1 (2) {
    ["ID"]=>
    int(1)
    ["parentID"]=>
    int(0)
  }
  [1]=>
  object(stdClass)#2 (2) {
    ["ID"]=>
    int(3)
    ["parentID"]=>
    int(2)
  }
  [2]=>
  object(stdClass)#3 (2) {
    ["ID"]=>
    int(2)
    ["parentID"]=>
    int(1)
  }
}

이 단일 차원 배열을 다차원 배열로 변환해야합니다. 나는 이것에 약간의 찌르기를 가져 갔지만 각 레벨의 둥지에 대한 루프가 없으면 완료 할 수있는 방법을 찾을 수 없습니다. 알고리즘은 가설 적으로 무한 수준의 중첩에 적응할 수 있어야합니다. 나는 몇 가지 재귀 기술을 사용해 보았지만 결코 옳은 적이 없습니다.

약간의 복잡성을 더하기 위해, 내가 얻는 배열의 객체는 항상 감각적 인 순서가 아닙니다. 위의 예에서 이것을 복제하려고 노력했습니다. ID 3 인 객체는 ID가 2의 객체 앞에 배열에 나오는 것을 알 수 있습니다. 따라서 그것들은 아마도 정렬 된 알고리즘이 될 것입니다.

이상적으로 위의 예는 다음과 같은 것으로 나타납니다.

Array
(
    [0] => Array
        (
            [ID] => 1
            [parentID] => 0
            [0] => Array
                (
                    [ID] => 2
                    [parentID] => 1
                    [0] => Array
                        (
                            [ID] => 3
                            [parentID] => 2
                        )

                )

        )

)

Answer 1

이 알고리즘을 시도하십시오.

// sort objects by parentID
function cmpNodes($a, $b) {
    return $a->parentID - $b->parentID;
}
usort($objects, 'cmpNodes');

// define first node as root of tree
$tree = (array) array_shift($objects);
// lookup table for direct jumps
$idTable = array($tree['ID'] => &$tree);
foreach ($objects as $object) {
    $node = (array) $object;
    // test if parent node exists
    if (!isset($idTable[$node['parentID']])) {
        // Error: parent node does not exist
        break;
    }
    // append new node to the parent node
    $idTable[$node['parentID']][] = $node;
    // set a reference in the lookup table to the new node
    $idTable[$node['ID']] = &$idTable[$node['parentID']][count($idTable[$node['parentID']])-3];
}
// unset($idTable);
var_dump($tree);

조회 테이블을 사용했습니다 ($idtable) ID가 노드로 직접 점프 할 수 있습니다.

Answer 2

따라서 선구자로서 - 나는 PHP를 전혀 모른다. 저는 주로 C 스타일 언어 개발자 (일명 C, 객관적인 C 및 Java)입니다. 따라서이 중 일부는 PHP에서 수행하기가 더 어려울 수 있지만 여기에 제가 시도 할 시도가 있습니다.

//the original input array
oldArray;
//the output array
array[] newArray = new array[];

foreach (element : oldArray) {
    //if the element is at the top, put it at the top of the array
    if (element.parentId == 0) {
        newArray.add(element);
    } else {
        //otherwise, find it's parent and put it in the child array of the parent
        for (potentialParent : oldArray) {
            if (potentialParent.id = element.parentId) {
                potentialParent.array.add(element);
                break;
            }
        }
    }
}

몇 가지 메모 : 나는 당신이 포인터로 모든 것을 전달한다고 가정합니다. 물체의 사본을 만드는 경우 어렵지만 불가능하지는 않습니다. 또한 배열의 크기를 동적으로 변경할 수 있다고 가정합니다. 다시 말하지만, 나는 PHP를 너무 알지 못합니다. 그렇게 할 수 없다면이 행동을 수행하는 절차 적 방법이 필요합니다. Java에서는 목록 유형을 사용하거나 배열을 복사하여 다시 재설정합니다.

이 알고리즘의 핵심은 아이들이 부모 아래에있는 곳 (어디에 있든) 한 번의 패스로 배치된다는 것입니다. 이것은 순서에 관계없이 해당 단일 패스에서 계층 구조가 생성 될 것임을 의미합니다. 예제에 표시되는 부모 주변의 래퍼 배열이 필요한 경우 코드 끝에 이와 같은 것을 추가 할 수 있습니다.

finalArray = new array[];
finalArray[0] = newArray;

도움이 되었기를 바랍니다.