10

I want simply to find-out better way to do this:

$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);

The goals is to print something like this:

a e h
a e i
a e j
a e k
a e l

a f h
a f i
a f j
a f k
a f l

a g h
a g i
a g j
a g k
a g l

Then doing same for b and c.

Currently, I am using this code:

foreach ($array[0] as $val1) {
    foreach ($array[1] as $val2) {
        foreach ($array[2] as $val3) {
            echo "$val1  $val2  $val3 \n";
        }
        echo "--------\n";
    }
}

I also tried to create above code dynamically and execute it with eval:

$eval         = '
     $data =array();
     ';
$eval_blocks  = '';
$eval_foreach = '';
$eval_data    = '
    $data[] = ';
$looplength   = count($array);

for ($i = 0; $i < $looplength; $i++) {
    $eval_foreach .= '
     foreach($array[' . $i . '] as $val' . ($i + 1) . '){
     ';
    if (($i + 1) == $looplength) {
        $eval_data .= ' $val' . ($i + 1) . ';';
    } else {
        $eval_data .= ' $val' . ($i + 1) . ' ." ".';
    }
    $eval_blocks .= '
     }
     ';
}
$eval = $eval . $eval_foreach . $eval_data . $eval_blocks;
eval($eval);
print_r($data);

But I still want to find better way for doing this, if possible.

Update:

Note: the $array is dynamic, It might contain two sub-array or more

7
  • 3 nested foreach loops is the way to go, since you are going to print ALL the possible combinations - there's no way to do it more efficiently.
    – Nir Alfasi
    Jul 30, 2013 at 23:27
  • But the $array might be dynamic, I want to create one general solution, I don't know how many elements and sub-array there
    – user1646111
    Jul 30, 2013 at 23:28
  • You can creat string from for and run eval!
    – ops
    Jul 31, 2013 at 1:01
  • 1
    Are you looking for a Cartesian Product algorithm?
    – deceze
    Aug 6, 2013 at 6:51
  • @deceze: Yes I satisfied with two answers there, lets see if others create new functions...
    – user1646111
    Aug 6, 2013 at 7:13

5 Answers 5

5
+100

I tried another approach but eventually ended with something similar to Valentin CLEMENT's solution although my function is more verbose.

Still, the originality is that this function gets you a tree of combinations, which may (or may not) be usefull depending on what you intend to do.

Here is the code :

function getCombinations( $arrayList, $index = 0  )
{
    $subCombinations = $combinations = '';

    if ( $index < count( $arrayList )-1 )
    {
        $subCombinations = getCombinations( $arrayList,  $index+1 );
    }

    foreach( $arrayList[$index] as $item )
    {
        $combinations[$item] = $subCombinations ;
    }
    return $combinations;
}

$combinations = getCombinations( $array );

print_r( $combinations );

With example data :

$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);

It will output :

Array
(
    [a] => Array
        (
            [e] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [f] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [g] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

        )

    [b] => Array
        (
            [e] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [f] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [g] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

        )

    [c] => Array
        (
            [e] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [f] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

            [g] => Array
                (
                    [h] => 
                    [i] => 
                    [j] => 
                    [k] => 
                    [l] => 
                )

        )

)

And then it requires additional code to draw expected result :

function drawCombinations( $combinations, $line = array() )
{
    foreach( $combinations as $value => $children )
    {
        array_push( $line, $value );

        if ( is_array( $children ) ) 
        {
            drawCombinations( $children, $line );
        }
        else
        { 
            echo implode( " ", $line ) ." \n";
        }

        array_pop( $line );
    }

}


drawCombinations( $combinations );

To produce :

a e h
a e i
a e j
a e k
a e l
a f h
a f i
a f j
a f k
a f l
a g h
a g i
a g j
a g k
a g l
b e h
b e i
b e j
b e k
b e l
b f h
b f i
b f j
b f k
b f l
b g h
b g i
b g j
b g k
b g l
c e h
c e i
c e j
c e k
c e l
c f h
c f i
c f j
c f k
c f l
c g h
c g i
c g j
c g k
c g l

As I said eariler, if you don't need this tree of results (that your questions did not mention, I just produced this while searching the best way), Valentin CLEMENT's approach could be better (if you don't use too large dataset, I will explain why after).

I rewrote it a bit, in a way I think more readable and usable :

function expand( $array, $from = 0, $length = false ) 
{
    if ( $length === false )
    {
        $length = count( $array );
    }

    if ( $length == $from )
    {
        return array('');
    }
    else 
    {
        $result = array();

        foreach( $array[$from] as $x ) 
        {
            foreach( expand( $array, $from+1, $length ) as $tail )
            {
                $result[] = trim("$x $tail");
            }
        }
        return $result;
    }
}


$combinations = expand( $array );

print_r( $combinations );

It returns the following array :

Array
(
    [0] => a e h
    [1] => a e i
    [2] => a e j
    [3] => a e k
    [4] => a e l
    [5] => a f h
    [6] => a f i
    [7] => a f j
    [8] => a f k
    [9] => a f l
    [10] => a g h
    [11] => a g i
    [12] => a g j
    [13] => a g k
    [14] => a g l
    [15] => b e h
    [16] => b e i
    [17] => b e j
    [18] => b e k
    [19] => b e l
    [20] => b f h
    [21] => b f i
    [22] => b f j
    [23] => b f k
    [24] => b f l
    [25] => b g h
    [26] => b g i
    [27] => b g j
    [28] => b g k
    [29] => b g l
    [30] => c e h
    [31] => c e i
    [32] => c e j
    [33] => c e k
    [34] => c e l
    [35] => c f h
    [36] => c f i
    [37] => c f j
    [38] => c f k
    [39] => c f l
    [40] => c g h
    [41] => c g i
    [42] => c g j
    [43] => c g k
    [44] => c g l
)

And it is then easy to achieve expected result :

echo implode( "\n", $combinations )."\n";

Will output :

a e h
a e i
a e j
a e k
a e l
a f h
a f i
a f j
a f k
a f l
a g h
a g i
a g j
a g k
a g l
b e h
b e i
b e j
b e k
b e l
b f h
b f i
b f j
b f k
b f l
b g h
b g i
b g j
b g k
b g l
c e h
c e i
c e j
c e k
c e l
c f h
c f i
c f j
c f k
c f l
c g h
c g i
c g j
c g k
c g l

I thought, at first, that my solution was cosuming more memory than Valentin's one because it uses arrays, but when I tested it out, I realized that it indeed it uses slightly less memory.

Displaying the memory metrics against the two methods gave those results :

drawCombinations(  getCombinations( $array ));

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

// 238736 244896





echo implode( "\n", expand( $array ) )."\n";

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

// 238912 252304

But it gets more important when using bigger input values, with :

$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l'),
    array('m', 'n', 'o', 'p', 'q', 'r', 's'),
    array('t', 'u', 'v', 'x', 'y', 'z')
);

getCombinations gives :

drawCombinations(  getCombinations( $array ));

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

// 242376 253008

expand gives :

echo implode( "\n", expand( $array ) )."\n";

echo memory_get_usage()." ". memory_get_peak_usage()."\n";

//242544 704520

The reason is obvious if we look at the array produced by each function, since the first solution stores less duplicate values (I am not sure how PHP handles the duplicates arrays ending each branch of the tree).

Once again, depending on what you plain to achieve, you will care or not.

"Echoing" each rows on the fly instead of creating a big result array decreases slightly the memory peak issue but expand() remains more memory consuming as dataset grows.

I hope it helps, at least that was interesting to me ;)

1
  • 1
    Nice analysis :) This is the first PHP I have written in my life, so I guess my version is FAR from optimal. I have no idea how it handles recursive calls and new arrays allocations, but the manual states: "It is possible to call recursive functions in PHP. However avoid recursive function/method calls with over 100-200 recursion levels as it can smash the stack and cause a termination of the current script.", which probably means it is wiser to not try recursion at all :)
    – val
    Aug 7, 2013 at 17:13
4

I first opted for some iteration (counting) based solution directly working on the arrays. As it turned out, this was just a loop with multiple counters. Then I thought, why limit this onto arrays? Why not using a CartesianProductIterator that creates an iteration over the cartesian product of multiple iterators?

It works similar to an AppendIterator and MultipleIterator (see as well: Iterating over Multiple Iterators at Once (Apr 2012; by hakre)) and can be easily used with your array:

$array = [
    ['a', 'b', 'c'],
    ['e', 'f', 'g'],
    ['h', 'i', 'j', 'k', 'l'],
];

$it = new CartesianProductIterator();

foreach($array as $sub)
{
    $it->append(new ArrayIterator($sub));
}

foreach ($it as $tuple)
{
    echo implode(',', $tuple), "\n";
}

The output is as expected:

a,e,h
a,e,i
a,e,j
...
c,g,j
c,g,k
c,g,l

A benefit of such an iterator is that it is more flexible for what it accepts as input.

Also those products can be extremely memory demaning, an iterator is a good tool to reduce memory requirements by solving the problem iteratively.

Another benefit is that an Iterator already keeps track of counting, so the counting problem per each dimension of the product is already solved.

As long as the memory consumption is concerned, instead of an iterator that implements the counting for you, you can do the iteration over all tuples in the product as well with a loop. This variant btw. should actually take care of keys, so should work with different inputs (the example code is reduced for reading):

...

// working loop
$valid = TRUE;
while ($valid)
{
    // create segment
    foreach ($array as $key => $sub)
    {
        echo $sub[$keys[$key][$counters[$key]]];
    }
    echo "\n";

    // count up
    foreach ($order as $key)
    {
        if (++$counters[$key] == $lengths[$key])
        {
            $counters[$key] = 0;
            continue;
        }
        continue 2;
    }
    $valid = FALSE;
};

As this example shows, each iteration in the loop outputs one tuple of the product, so memory requirements are low, too. If you replace the echo with a yield statement this is a good boilerplate to create a generator from.

As the CartesianProdcutIterator is an object so it can do a little more than a loop or generator, therefore it has some more features: You can specify the iteration or counting or sort mode: Move on the last iterator first (default), or the first first:

$it = new CartesianProductIterator(CartesianProductIterator::ORDER_FIRST_FIRST);

This will do the following iteration:

a,e,h
b,e,h
c,e,h
...
a,g,l
b,g,l
c,g,l

But not only that, it can be even controlled more by specifying a $countOrder parameter when appending. It specifies the actual sort-keys to be ordered on by the order-mode:

$array = [
    0 => ['a', 'b', 'c'],
    2 => ['e', 'f', 'g'],
    1 => ['h', 'i', 'j', 'k', 'l'],
];

$it = new CartesianProductIterator();

foreach($array as $countOrder => $sub)
{
    $it->append(new ArrayIterator($sub), $countOrder);
}

foreach ($it as $tuple)
{
    echo implode(',', $tuple), "\n";
}

This (as the default mode is last-first) specifies to first iterate in the middle (e-g), then at the end (h-l) and then on the first one (a-c):

a,e,h
a,f,h
a,g,h
a,e,i
...
c,g,k
c,e,l
c,f,l
c,g,l

Hope this is helpful and qualifies as "a better way".

1
1

This should work:

function expand($arr){
    function recexpand($arr, $from, $len) {
        if ($from == $len) {
            yield "\n";
        } else {
            foreach($arr[$from] as $x) {
                foreach(expand($arr, $from+1, $len) as $tail) {
                    yield "$x $tail";
                }
            }
        }
    }
    return recexpand($arr, 0, count($arr);
}
$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);
foreach(expand($array) as $row) {
    echo $row;
}

echoes:

a e h
a e i
a e j
a e k
a e l
a f h
a f i
a f j
a f k
a f l
a g h
a g i
a g j
a g k
a g l
b e h
b e i
b e j
b e k
b e l
b f h
b f i
b f j
b f k
b f l
b g h
b g i
b g j
b g k
b g l
c e h
c e i
c e j
c e k
c e l
c f h
c f i
c f j
c f k
c f l
c g h
c g i
c g j
c g k
c g l

I'm not a PHP guy, so there is probably a more idiomatic way to write it, but it will work for any length of the array.

For PHP<5 (or any version which has no 'yield' statement)

function expand($arr) {
    function recexpand($arr, $from, $len) {
        if ($from == $len) {
            return array("\n");
        } else {
            $result = array();
            foreach($arr[$from] as $x) {
                foreach(expand($arr, $from+1, $len) as $tail) {
                    $result[] = "$x " . $tail;
                }
            }
            return $result;
        }
    }
    return recexpand($arr, 0, count($arr));
}
$arr = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);
foreach(expand($arr) as $row) {
    echo "$row";
}
7
  • yield switches the control flow to the caller function, and then continues to execute code.
    – val
    Aug 6, 2013 at 12:46
  • 1
    It is documented here for PHP: php.net/manual/en/language.generators.syntax.php
    – val
    Aug 6, 2013 at 12:46
  • If you wanted to iterate over an array, you could have: function iterover($array) { for($i = 0; $i < count($array); $i++) { yield $array[$i]; } } $array = array(1,2,3) $generator = iterate($array) Calling the generator once will yield the first value (1), but will keep the function 'alive' and the current value of $i. Calling it again will yield '2', and so on. The internal state of the function is preserved between each call.
    – val
    Aug 6, 2013 at 12:51
  • thanks, but it seems that yield requires PHP >=(PHP 5 >= 5.5.0)
    – user1646111
    Aug 6, 2013 at 12:54
  • Well, you can obtain the same effect by passing around arrays. See my edit
    – val
    Aug 6, 2013 at 13:12
1

I'm impressed about the great algorithms you guys came up with. However i think that the right method in PHP, is to use an Iterator: http://php.net/manual/fr/class.iterator.php

I implemented an example of what you could do for your problem.

class CombinationIterator implements Iterator {
    private $position = 0;
    private $array = array();

    public function __construct($array) {
        $this->array = $array;
        $this->position = array_fill(0,sizeof($this->array),0);
    }

    function rewind() {
        $this->position = array_fill(0,sizeof($this->array),0);
    }

    function current() {
        $word = array();
        foreach ($this->position as $i=>$pos) {
            $word[]=$this->array[$i][$pos];
        }
        return implode(" ",$word);
    }

    function key() {
        return $this->position;
    }
    function next() {
        foreach (array_reverse($this->position,true) as $i=>$pos) {
            # if position in this array has reached end, set it to 0 and increse next one
            if ($pos == sizeof($this->array[$i])-1) {
                $this->position[$i] = 0;
                if (array_key_exists($i-1,$this->position)) {
                    continue;
                } else {
                    $this->rewind();
                }
                break;
            } else {
                $this->position[$i]++;
                break;
            }

        }
    }
    function valid() {
        $valid = false;
        foreach ($this->position as $i=>$pos) {
            if ($pos < sizeof($this->array[$i])-1) { return true; }
        }
        return $valid;
    }

}

And here is how you could use it to display your words :

$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l'),
    array('m', 'n', 'o', 'p', 'q', 'r', 's'),
    array('t', 'u', 'v', 'x', 'y', 'z')
);


$c = new CombinationIterator($array);
while ($c->valid()) {
    echo $c->current()."\n";
    $c->next();
}

I didn't write the previous() method, but you can easily create it from the next() method.

Also memory usage is very low here because you only get the position stored.

I hope it can help you for your project.

Bye

3
  • God job, what is the best method to repeat same work for other elements, for example we only considered first array(a, b, c) to be joined with others, what if I want to shift $array[0] with $array[1] then its prints e a h m t and so on...
    – user1646111
    Aug 10, 2013 at 1:36
  • I'm sorry, i didn't understand your question. You want to invert $array[0] and $array[1] ? You want to do it one time or dynamically ? From this iterator, you could still use some algorithm to generate the array you want and pass it to the iterator.
    – Thibault
    Aug 12, 2013 at 9:05
  • when using your iterator in a foreach, it doesn't print the last element. Dec 21, 2016 at 23:24
1

My non-recursive way:

<?php
$array = array(
    array('a', 'b', 'c'),
    array('e', 'f', 'g'),
    array('h', 'i', 'j', 'k', 'l')
);

$upperBounds = array();
foreach ($array as $arr) {
    $upperBounds[] = count($arr);
}

$counterArray = array_pad(array(), count($array), 0);

do {
    foreach ($counterArray as $key => $c) {
        echo $array[$key][$c];
    }
    echo PHP_EOL;
} while (incrementCounter($counterArray, $upperBounds));

function incrementCounter(&$counterArray, $upperBounds)
{
    if (count($counterArray) == 0 || count($counterArray) != count($upperBounds)) {
        return false;
    }
    $counterArray[0]++;
    foreach ($counterArray as $key => $value) {
        if ($counterArray[$key] >= $upperBounds[$key]) {
            $counterArray[$key] = 0;
            if (isset($counterArray[$key+1])) {
                $counterArray[$key+1]++;
            }
            else {
                $counterArray[$key+1] = 1;
                return false;
            }
        }
        else {
            break;
        }
    }
    return true;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.