Solution and forked from https://gist.github.com/830201

algorithm.php

<?php

$arr = array(
	'Color' => array('Red', 'Blue'),
	'Size' => array('Regular', 'Large'),
	'Material' => array('Metalic', 'Nylon')
);

function magic_algorithm($arr){
    function cartesian_product($arrays) {
        $result = array();

        if (count($arrays) == 0) {
            return array(array());
        }

        reset($arrays);
        $first_key = key($arrays);
        $first_array = array_shift($arrays);

        $rec = cartesian_product($arrays);

        foreach ($first_array as $v) {
            foreach ($rec as $tail) {
                $result []= array_merge(array($first_key => $v), $tail);
            }
        }

        return $result;
    }

    $product = cartesian_product($arr);

    $result = array();
    foreach ($product as $row) {
        $line = array();
        foreach ($row as $key => $val) {
            $line []= "$key: $val";
        }
        $result []= join("; ", $line);
    }
    return $result;
}


$result = magic_algorithm($arr);

$expected = array(
	"Color: Red; Size: Regular; Material: Metalic",
	"Color: Red; Size: Regular; Material: Nylon",

	"Color: Red; Size: Large; Material: Metalic",
	"Color: Red; Size: Large; Material: Nylon",

	"Color: Blue; Size: Regular; Material: Metalic",
	"Color: Blue; Size: Regular; Material: Nylon",

	"Color: Blue; Size: Large; Material: Metalic",
	"Color: Blue; Size: Large; Material: Nylon"
);


echo ($expected == $result) ? "Passed" : "Failed";
print_r($result);
echo "\n";