シングル次元配列のデータを用いたアルゴリズムで多次元配列を作成します。

Question

私はPHPオブジェクトの単一次元アレイを有します。各オブジェクトは、1つの属性は、オブジェクトの一意のIDであり、他方は、その親である配列内の別のオブジェクトの一意のIDで、2つの属性があります。たとえばます：

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

Iは、多次元配列にこの単一次元配列に変換する必要があります。私はこの時に、いくつかのスタブをとっているが、私はそれは、ネストのレベルごとにループを持たずに成し遂げるための方法を見つけることができません。このアルゴリズムは、ネストの仮想的に無限のレベルに適応できるようにする必要があります。私はいくつかの再帰技術を使用してみましたが、私はそれは全く正しい得たことがありません。

複雑さのビットを追加するには、私が取得しています配列内のオブジェクトは無意味ために常にではありません。私は上記の私の例でこれを複製しようとしました。あなたは、2のIDを持つオブジェクトだからおそらく同様に関与ソートアルゴリズム自分なりの前に3のIDを持つオブジェクトが配列で来ることがわかります。

理想的には、上記の例では、このような何かを消すだろう

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

Iノードに直接ジャンプするIDのルックアップテーブル（$idtable）を使用します。

Answer 2

それでは、前駆体として - 私は本当にすべてで、PHPを知りません。私は主にCスタイルの言語の開発者（別名C、Objective 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では、私はリストタイプを使用するか、または単にアレイをコピーし、それを再度リセットします。

どこにいても - - 1回のパスで、

このアルゴリズムの作業への鍵は、子どもが親の下に配置されていることです。これは関係なく順番、階層がその単一のパスで作成されず、ということを意味します。あなたはあなたの例で示した親ラッパーの配列が必要な場合は、単にコードの最後に、このようなものを追加することができます：

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

この情報がお役に立てば幸いです。