Calculate pairs in tree function

[Nuv]

I have an array whose each element is like 3632873_1_right or 3632873_1_left where 3632873 is the member ID , 1 is the level in the binary tree and left/right is the position in the tree i.e right child or left child. I would like to calculate pair in each level . 1 right and 1 left in a level is considered as a pair. So suppose in level 1 there are 2 ids (in the array shown below) 3632873 and 5951538.3632873 is right child and 5951538 is left child. Thus level 1 has one pair. However in level 2 there are 2 elements 8930480 and 7563232, but both of them are left child. Thus there are no pairs in level 2. Finally i need the total number of pairs adding pairs of each level.I am trying to make a function for it, however i'm not getting how to. Can someone please point me how can i do so ?

 

Array
(
    [0] => 3632873_1_right
    [1] => 5951538_1_left
    [2] => 8930480_2_left
    [3] => 7563232_2_left
)

[xyph]

I'd like to see how this array is being populated - that would probably be a better place to do this, but here it goes!

 

<?php

// create some random data
$data = array();
for( $i=0;$i<15;$i++ ) $data[] = $i.'_'.mt_rand(1,5).'_'.(mt_rand(0,1)==1?'right':'left');

// this is the part you want
$data_sort = array();
foreach( $data as $mixed ) {
list($id,$level,$side) = explode('_',$mixed);
$data_sort[$level][$id] = $side;
}

ksort($data_sort);

foreach( $data_sort as $level => $id ) {
echo "<b>Dumping data for level $level</b><ul>";
if( in_array('left',$id) && in_array('right',$id) )
	echo "<li>There are right and left sides</li>";
else
	echo "<li>All IDs are on one side</li>";
asort($id); $right=''; $left='';
foreach( $id as $num => $side ) $$side .= $num.', ';
echo "<li>Left IDs: $left</li>";
echo "<li>Right IDs: $right</li>";
echo "</ul>";
}

?>

 

You could probably avoid a few loops unless the array is being populated from a source outside of your control

[Nuv]

I extended your code to get the count level wise for each side.Thankyou man . Also would you like to see the function with which this array is being populated ?

 

$data = array();
for( $i=0;$i<15;$i++ ) $data[] = $i.'_'.mt_rand(1,5).'_'.(mt_rand(0,1)==1?'right':'left');


$data_sort = array();
foreach( $data as $mixed ) {
    list($id,$level,$side) = explode('_',$mixed);
    $data_sort[$level][$id] = $side;
}

ksort($data_sort);

foreach( $data_sort as $level => $id ) {
    echo "<b>Dumping data for level $level</b><ul>";
    if( in_array('left',$id) && in_array('right',$id) )
        echo "<li>There are right and left sides</li>";
    else
        echo "<li>All IDs are on one side</li>";
    asort($id); $right=''; $left='';
    foreach( $id as $num => $side ) $$side .= $num.', ';
    echo "<li>Left IDs: $left</li>";
    echo "<li>Right IDs: $right</li>";
    echo "</ul>";
    $put_left[] = $left;
    $put_right[] = $right;
    
}

$count_left = count($put_left);
for($i = 0 ; $i < $count_left ; $i++)
{
  $pieces =  explode(", ", $put_left[$i]);
  $final_count = count($pieces) - 1;  
  $final_left[$i+1]  = $final_count;
}
$count_right = count($put_right);
for($i = 0 ; $i < $count_right ; $i++)
{
  $pieces =  explode(", ", $put_right[$i]);
  $final_count = count($pieces) - 1;  
  $final_right[$i]  = $final_count;
}

echo "<pre>";
print_r($final_left);
print_r($final_right);

echo "</pre>"; 

 

[xyph]

You don't need these lines

 

$data = array();
for( $i=0;$i<15;$i++ ) $data[] = $i.'_'.mt_rand(1,5).'_'.(mt_rand(0,1)==1?'right':'left');

 

That simply populates a bunch of sample data for me to use to test the script.

 

Unless you are using that data elsewhere, a lot of the sorting could be done when you populate the script, saving at least 1 loop.

 

Finding the number of pairs is easy, simple logic. If a given level has results on both sides, then number of pairs is equal to the number of results in the lesser side. In code, that would be

 

<?php

// create some random data
$data = array();
for( $i=0;$i<20;$i++ ) $data[] = $i.'_'.mt_rand(1,5).'_'.(mt_rand(0,1)==1?'right':'left');

// this is the part you want
$data_sort = array();
foreach( $data as $mixed ) {
list($id,$level,$side) = explode('_',$mixed);
$data_sort[$level][$id] = $side;
}

ksort($data_sort);

$pairs = 0;
foreach( $data_sort as $level => $id ) {
echo "<b>Dumping data for level $level</b><ul>";
if( in_array('left',$id) && in_array('right',$id) )
	echo "<li>There are right and left sides</li>";
else
	echo "<li>All IDs are on one side</li>";
asort($id); $right=''; $left=''; $right_count = 0; $left_count = 0;
foreach( $id as $num => $side ) {
	$$side .= $num.', ';
	${$side.'_count'}++;
}
$set_pairs = $right_count > $left_count ? $left_count : $right_count;
$pairs += $set_pairs;
echo "<li>Left IDs: $left</li>";
echo "<li>Right IDs: $right</li>";
echo "<li>Number of pairs: $set_pairs</li>";
echo "</ul>";
}

echo "<b>Total pairs: $pairs</b>";

?>

 

If my use of variable variables here has confused you, i can rewrite it using arrays, which might make things a little more simple.

[Nuv]

You don't need these lines

 

$data = array();
for( $i=0;$i<15;$i++ ) $data[] = $i.'_'.mt_rand(1,5).'_'.(mt_rand(0,1)==1?'right':'left');

 

Yeah i understand that. I just used them to show you that i extended the code.

 

Finding the number of pairs is easy, simple logic. If a given level has results on both sides, then number of pairs is equal to the number of results in the lesser side. In code, that would be

 

<?php

// create some random data
$data = array();
for( $i=0;$i<20;$i++ ) $data[] = $i.'_'.mt_rand(1,5).'_'.(mt_rand(0,1)==1?'right':'left');

// this is the part you want
$data_sort = array();
foreach( $data as $mixed ) {
list($id,$level,$side) = explode('_',$mixed);
$data_sort[$level][$id] = $side;
}

ksort($data_sort);

$pairs = 0;
foreach( $data_sort as $level => $id ) {
echo "<b>Dumping data for level $level</b><ul>";
if( in_array('left',$id) && in_array('right',$id) )
	echo "<li>There are right and left sides</li>";
else
	echo "<li>All IDs are on one side</li>";
asort($id); $right=''; $left=''; $right_count = 0; $left_count = 0;
foreach( $id as $num => $side ) {
	$$side .= $num.', ';
	${$side.'_count'}++;
}
$set_pairs = $right_count > $left_count ? $left_count : $right_count;
$pairs += $set_pairs;
echo "<li>Left IDs: $left</li>";
echo "<li>Right IDs: $right</li>";
echo "<li>Number of pairs: $set_pairs</li>";
echo "</ul>";
}

echo "<b>Total pairs: $pairs</b>";

?>

 

If my use of variable variables here has confused you, i can rewrite it using arrays, which might make things a little more simple.

 

Gah ! i knew there was a better way. Though i wanted to put in my effort.

[xyph]

No problem. If there's any part of the code you don't understand, feel free to ask and I can elaborate.

 

I will avoid writing long blocks of comments if i can, though