Эффективный алгоритм PHP для генерации всех комбинаций/перестановок входов

Question

Я пытаюсь вычислить все комбинации набора значений в массиве для нескольких входов. Подобно этому вопросу:

PHP algorithm to generate all combinations of a specific size from a single set

Например:

function sampling($chars, $size, $combinations = array()) { 

    if (empty($combinations)) { 
     $combinations = $chars; 
    } 

    if ($size == 1) { 
     return $combinations; 
    } 

    $new_combinations = array(); 

    foreach ($combinations as $combination) { 
     foreach ($chars as $char) { 
      $new_combinations[] = $combination . $char; 
     } 
    } 
    return sampling($chars, $size - 1, $new_combinations); 
} 

$chars = array('a', 'b', 'c'); 
$output = sampling($chars, 2); 
echo implode($output,', '); 

Выход:

aa, ab, ac, ba, bb, bc, ca, cb, cc 

Но беда в том, когда я сползать это до большего списка, например:

$chars = array('a', 'b', 'c', 'd'); 
$output = sampling($chars, 12); 

Число перестановок резко возрастает, и у PHP заканчивается память. По-видимому, решение этого - использовать генераторы и давать результаты во время цикла. Единственные примеры генераторов, хотя и являются для несколько иной задачи устанавливает:

См: https://stackoverflow.com/a/27160465/345086

Любые идеи о том, как использовать генераторы, чтобы решить эту проблему?

Answer 1

Дайте этому выстрел:

<?php 
$chars = array('a','b','c'); 
$count = 13; 

$generator = genCombinations($chars,$count); 
foreach ($generator as $value) { 
    // Do something with the value here 
    echo $value; 
} 

function genCombinations($values,$count=0) { 
    // Figure out how many combinations are possible: 
    $permCount=pow(count($values),$count); 

    // Iterate and yield: 
    for($i = 0; $i < $permCount; $i++) 
    yield getCombination($values, $count, $i); 
} 

// State-based way of generating combinations: 
function getCombination($values, $count, $index) { 
    $result=array(); 
    for($i = 0; $i < $count; $i++) { 
    // Figure out where in the array to start from, given the external state and the internal loop state 
    $pos = $index % count($values); 

    // Append and continue 
    $result[] = $values[$pos]; 
    $index = ($index-$pos)/count($values);; 
    } 
    return $result; 
} 

Это состояние на основе фиксированной длины комбинации генератор, который, будем надеяться соответствовать требованиям. Он будет принимать только массивы и будет возвращать комбинации элементов массива, независимо от того, что на самом деле хранится в массиве.