gistfile1.txt

function cartesianProduct(array $arrayOfSets, array $tuple = array(), $n = 0) {
    $size = count($arrayOfSets);
    if ($n === $size) {
        return array();
    }

    $result = array();
    $set = $arrayOfSets[$n];
    foreach($set as $itemOfSet) {
        // добавляем элемент множества в н-ку
        array_push($tuple, $itemOfSet);
        // рекурсивно вызываем метод, который начинает обход со следующего множества в наборе
        if (($n + 1) === $size) {
            $result []= array_slice($tuple, 0);
        } else {
            $resultOfNextSets = cartesianProduct($arrayOfSets, $tuple, $n + 1);
            foreach ($resultOfNextSets as $set) {
                $result []= array_slice($set, 0);
            }
        }

        array_pop($tuple);
    }

    return $result;
}