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

Question

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

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

Алгоритм PHP для генерации всех комбинаций определенного размера из одного набора

Например:

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

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

2

php php-generators

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Дайте этому шанс:

<?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;
}

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

4