current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote -3 down vote favorite

I have problem with make automatic tree of arrays in PHP. Ex. i have numbers in my array: 2, 3, 3, and i can manulally make tree.

<?
$source_arr = array(2,3,3);

for($x=0; $x<$source_arr[0]; $x++){ // level 0: 2 loops

for ($xx=0; $xx<$source_arr[1]; $xx++) {  // level 1: 3 loops

    for ($xxx=0; $xxx<$source_arr[2]; $xxx++) {  // level 2: 3 loops

        $new[] = "$x$xx$xxx";

   }    
    }
}   

echo "<pre>";
print_r($new);
echo "</pre>";

?>

result:

Array
(
    [0] => 000
    [1] => 001
    [2] => 002
    [3] => 010
    [4] => 011
    [5] => 012
    [6] => 020
    [7] => 021
    [8] => 022
    [9] => 100
    [10] => 101
    [11] => 102
    [12] => 110
    [13] => 111
    [14] => 112
    [15] => 120
    [16] => 121
    [17] => 122
)

But i want to automate it, i have different numbers of levels arrays with different values, like this: 11 levels:

$source_arr = array(8,5,10,12,5,8,12,5,6,10,8);

And i want to build automatic large tree. Is it possible with PHP array_walk or array_walk_recursive ? I found posts about building recursive categories tree, but i can not adapt those codes.

edit: i do not want to do infinity array and achieve memory exhaustion. My array count is never larger than 15 items, values range: 3-16.

share|improve this question
1  
What are you trying to achieve? –  JvdBerg Sep 29 '12 at 14:44
3  
@jvdberg: memory exhaustion? –  Mark Reed Sep 29 '12 at 14:44
1  
First, your result is not a tree; it's a flat array containing all the combinations. Is that what you're looking for? Second, do you really need to store all of the possible combinations (in your example, 5,529,600,000 of them) in memory, or do you just need to loop over them and do something for each one? –  Mark Reed Sep 29 '12 at 14:50
    
@user1708401 can i just ask what the tree would be used for ?? –  Baba Sep 29 '12 at 14:51
1  
@Syntax Error this problem looks like another one: finding the probabilities that by casting some dices which could have different number of faces, the sum of these dices is equal to some integer. This is the multinomial distribution, but you can compute it this way. –  Valentin Perrelle Sep 29 '12 at 15:26

2 Answers 2

up vote 3 down vote

Iterating through trees have to be done recursively. There is no choice since tree depth is unbounded but your loop nesting level is fixed. You are not building the tree, but the construction of your list is indeed a tree traversal. Your recursive function must have the following parameters :

  • an identification of the current node, here, we can just use the level of the node and the prefix string built from its parent ;
  • the size of each level of the tree, which can be retrieve from your list of array source_arr and the current level already provided ;
  • the array being built

The result could also have been produced by return and merge, but it wouldn't be more simple and it would be less efficient.

<?php

function build(array &$sizes, array &$result, $prefix, $level)
{
  if ($level == count($sizes)) {
    $result[] = $prefix;
  }
  else {
    for ($i = 0 ; $i < $sizes[$level] ; $i++) {
      build($sizes, $result, $prefix . $i, $level + 1);
    }
  }
}


$sizes = array(8,5,10,12);
$result = array();
build($sizes, $result, '', 0);

echo "<pre>";
print_r($result);
echo "</pre>";

?>

Note that the tree you are requesting is huge, and PHP will run out of memory before being able to print the result.

share|improve this answer
    
This is exactly the solution I wanted. Thank you very much for help. –  user1708401 Sep 29 '12 at 15:47
up vote 0 down vote

Here's another solution that seems to be working. It's not very clean, I know. But hey! There's no recursion! ;)

<?php

function generate(array $a) {
  $multArray = function($mult, $e) {
    return $mult * $e;
  };

  $finalSize = array_reduce($a, $multArray, 1);

  $res = array();
  $aReverse = array_reverse($a);
  for ($i = 0; $i < $finalSize; $i++) {
    $tmpReverseRes = array();
    foreach ($aReverse as $k => $v) {
      $mult = array_reduce(array_slice($aReverse, 0, $k), $multArray, 1);
      $tmpReverseRes[] = (int)($i / $mult) % $v;
    }
    $res[] = join('', array_reverse($tmpReverseRes));
  }

  return $res;
}

$a = array(2, 3, 3);

print_r(generate($a));

update:

We can also implement that with a class:

<?php
class StrangeGenerator {
  private $a = null;
  private $aReverse = null;
  private $combinationsCount = null;

  public function __construct(array $array) {
    $this->a = $array;
    $this->aReverse = array_reverse($array);
    $this->combinationsCount = array_reduce($array, 'self::multArray', 1);
  }

  public function getCombinationFor($index) {
    $this->checkRange($index);

    $revRes = array();
    foreach ($this->aReverse as $k => $v) {
      $mult = array_reduce(array_slice($this->aReverse, 0, $k), 'self::multArray', 1);
      $revRes[] = (int)($index / $mult) % $v;
    }
    return join('', array_reverse($revRes));
  }

  public function getCombinationsCount() {
    return $this->combinationsCount;
  }

  protected function checkRange($index) {
    if ($index < 0 || $index >= $this->combinationsCount) {
      throw new RangeException('Out of range');
    }
  }

  protected static function multArray($mult, $e) {
    return $mult * $e;
  }
}

$a = array(2, 3, 3);

$g = new StrangeGenerator($a);

$count = $g->getCombinationsCount();

for ($i = 0; $i < $count; $i++) {
  $res = $g->getCombinationFor($i);
  echo "$res\n";
}

Btw, this class does not keep all the combinations in the memory. They're calculated on demand instead.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.