php build strings from array elements

Question

I`ve got the following array:

$myarray = array( 
    2 => array( 
        'id' => '2', 
        'parent_id' => '1', 
    ),  
    4 => array( 
        'id' => '4', 
        'parent_id' => '2', 
    ), 
    3 => array( 
        'id' => '3', 
        'parent_id' => '1', 
    ), 
    1 => array( 
        'id' => '1', 
        'parent_id' => '0', 
    ) 
);

and the goal is to have the following output:

1 
1.2 
1.2.4  
1.3

The problem is that I need to do that without recursion. Here is some kind of an answer but the guys there are building tree while I need to have strings. I tried to use some kind of $basestring variable in order to know where am I, but still it did not work without recursion. Any ideas how to do that?

Thank you

UPD My first attempt was the following:

foreach($myarray as $k=>$value){
 if($value['parent_id'] == 0){
    $string = '1';
    $id = $value['id'];
    $newarr[0] = $string;
    $basestring = $string.'.';
 }elseif($value['parent_id'] == 1){
    $string = $basestring.$value['id'];
    $id = $value['id'];
    $newarr[$id] = $string;
 }elseif($value['one'] == 2){
    $string = $basestring.$value['parent_id'].'.'.$value['id'];
    $id = $value['id'];
    $newarr[$id] = $string;
 }elseif($value['parent_id'] == 3){
    $string = $basestring.$value['parent_id'].'.'.$value['id'];
    $id = $value['id'];
    $newarr[$id] = $string;
 }elseif($value['parent_id'] == 4){
    $string = $basestring.$value['parent_id'].'.'.$value['id'];
    $id = $value['id'];
    $newarr[$id] = $string;
   }//etc...
  }
}

but obviously it failed due to non-scalability. I need to code somehow the iteration from child to parent here

Why the arbitrary requirement of _without recursion_? What have you tried? Using recursion is just one way of solving a problem. Anything you can do with a recursive approach you can do with an iterative approach. Showing what you tried and failed at only serves to make the question more specific so that the answer can be more useful. Otherwise, it easily becomes too broad. — Sherif, Aug 26 '16 at 17:59
There are some requirements for the amount of memory used for this task. If the array becomes to large it may run out of memory. The problem is that I cannot build strings each time from the beginning without recursion — Jack, Aug 26 '16 at 18:05
Well, you _can_. The question is what did you try that resulted in you concluding that you couldn't because you failed. That usually helps narrow down the problem to a more specific use case where the answer than becomes more useful and fitting. — Sherif, Aug 26 '16 at 18:06
Here's why I'm asking to more vociferously express the ambiguity of your question: If your no-recursion requirement is about memory, specifically the size of the array; then how do you get the array in PHP? __This implies that you don't have the array in memory in the first place__. Now the question actually needs further clarification. Did you mean you're only loading a small subset of the tree as an array at a time? If so how? Where's the code that does that? See why showing your work is very important here? — Sherif, Aug 26 '16 at 18:11

Don't Panic · Accepted Answer · 2016-08-26T18:43:12.550

3

An iterative solution could work something like this:

foreach ($myarray as $x) {
    $temp = $x;
    $string = [];

    while (true) {
        $string[] = $temp['id'];                            // add current level id
        if (!isset($myarray[$temp['parent_id']])) break;    // break if no more parents
        $temp = $myarray[$temp['parent_id']];               // replace temp with parent
    }

    $strings[] = implode('.', array_reverse($string));
    // array_reverse is needed because you've added the levels from bottom to top
}

Basically for each element of the array, create a temporary copy, then find its parents by key and set the temporary copy to the parent until no more parents are found. Add the ids into an array as you go and build the string from the array when you get to the end.

This assumes your array is valid, in that it does not contain circular references (e.g. one level being its own ancestor). To prevent an infinite loop if this did happen, you could increment a variable within the while loop and break if it reached some reasonable limit.

edited Aug 26 '16 at 18:43

answered Aug 26 '16 at 18:37

Don't Panic

41,125
10
61
80

Thank You, it works. Is there a way to sort it out by values somehow? It produces the result as the keys in the initial array go. – Jack Aug 26 '16 at 18:44
What if they are not in any order at all? Might want to `ksort()` first. Then no need for `array_reverse()`. – AbraCadaver Aug 26 '16 at 19:11
@AbraCadaver I think this way doesn't depend on it being in order. I may be misunderstanding you. Wouldn't it still need to go start with child elements and work up through their parents even if you ksorted the array beforehand? If you don't mind explaining a bit more I'd like to improve the answer if I can. – Don't Panic Aug 26 '16 at 19:51

php build strings from array elements

1 Answers1