Как вычислить декартову мощность ряда символов?
Я хотел бы создать функцию, способную генерировать список букв и необязательных цифр, используя a-z, 0-9.
$output = array();
foreach(range('a','z') as $i) {
foreach(range('a','z') as $j) {
foreach(range('a','z') as $k) {
$output[] =$i.$j.$k;
}
}
}
Спасибо
Пример:
myfunction($include, $length)
Используйте что-то вроде этого:
myfunction('a..z,0..9', 3);
Вывод:
000
001
...
aaa
aab
...
zzz
Вывод будет содержать все возможные комбинации букв и цифр.
4 answers
Подготовка сцены
Во-первых, функция, которая расширяет строки, такие как "0..9", до "0123456789", используя range:
function expand_pattern($pattern) {
$bias = 0;
$flags = PREG_SET_ORDER | PREG_OFFSET_CAPTURE;
preg_match_all('/(.)\.\.(.)/', $pattern, $matches, $flags);
foreach ($matches as $match) {
$range = implode('', range($match[1][0], $match[2][0]));
$pattern = substr_replace(
$pattern,
$range,
$bias + $match[1][1],
$match[2][1] - $match[1][1] + 1);
$bias += strlen($range) - 4; // 4 == length of "X..Y"
}
return $pattern;
}
Он обрабатывает любое количество расширяемых шаблонов и заботится о том, чтобы сохранить их положение внутри исходной строки, например
expand_pattern('abc0..4def5..9')
Вернется "abc01234def56789".
Вычисление результата сразу
Теперь, когда мы можем легко выполнить это расширение, вот функция, которая вычисляет декартовы произведения с учетом строки допустимых символы и длина:
function cartesian($pattern, $length) {
$choices = strlen($pattern);
$indexes = array_fill(0, $length, 0);
$results = array();
$resets = 0;
while ($resets != $length) {
$result = '';
for ($i = 0; $i < $length; ++$i) {
$result .= $pattern[$indexes[$i]];
}
$results[] = $result;
$resets = 0;
for ($i = $length - 1; $i >= 0 && ++$indexes[$i] == $choices; --$i) {
$indexes[$i] = 0;
++$resets;
}
}
return $results;
}
Так, например, чтобы получить результат, описанный в вопросе, вы бы сделали
$options = cartesian(expand_pattern('a..z0..9'), 3);
Увидеть это в действии ( Я ограничил длину расширения до 2, чтобы выход не взорвался).
Генерация результата на лету
Поскольку результирующий набор может быть чрезвычайно большим (он растет экспоненциально с $length), получение всего этого сразу может оказаться непомерно большим. В этом случае можно переписать код так что он возвращает каждое значение по очереди (в стиле итератора), что стало очень просто с PHP 5.5 из-за генераторов :
function cartesian($pattern, $length) {
$choices = strlen($pattern);
$indexes = array_fill(0, $length, 0);
$resets = 0;
while ($resets != $length) {
$result = '';
for ($i = 0; $i < $length; ++$i) {
$result .= $pattern[$indexes[$i]];
}
yield $result;
$resets = 0;
for ($i = $length - 1; $i >= 0 && ++$indexes[$i] == $choices; --$i) {
$indexes[$i] = 0;
++$resets;
}
}
}
Смотрите этот ответ для кода, который создает все возможные комбинации: https://stackoverflow.com/a/8567199/1800369
Вам просто нужно добавить параметр $length, чтобы ограничить размер комбинаций.
Вы можете использовать рекурсивную функцию
Предполагая, что вы имеете в виду, что это может быть любое количество уровней, вы можете использовать рекурсивную функцию для создания массива перестановок, например:
/**
* take the range of characters, and generate an array of all permutations
*
* @param array $range range of characters to itterate over
* @param array $array input array - operated on by reference
* @param int $depth how many chars to put in the resultant array should be
* @param int $currentDepth internal variable to track how nested the current call is
* @param string $prefix internal variable to know what to prefix the current string with
* @return array permutations
*/
function foo($range, &$array, $depth = 1, $currentDepth = 0, $prefix = "") {
$start = !$currentDepth;
$currentDepth++;
if ($currentDepth > $depth) {
return;
}
foreach($range as $char) {
if ($currentDepth === $depth) {
$array[] = $prefix . $char;
continue;
}
foo($range, $array, $depth, $currentDepth, $prefix . $char);
}
if ($start) {
return $array;
}
С помощью вышеуказанной функции инициализируйте возвращаемую переменную и вызовите ее:
$return = array();
echo implode(foo(range('a', 'z'), $return, 3), "\n");
И вы выведете все три комбинации символов от aaa до zzz:
aaa
aab
...
zzy
zzz
Числовой параметр определяет, насколько рекурсивна функция:
$return = array();
echo implode(foo(range('a', 'z'), $return, 1), "\n");
a
b
c
...
$number= range(0, 9);
$letters = range('a', 'z');
$array= array_merge($number, $letters);
//print_r($array);
for($a=0;$a<count($array);$a++){
for($b=0;$b<count($array);$b++){
for($c=0;$c<count($array);$c++){
echo $array[$a].$array[$b].$array[$c]."<br>";
}
}
}
Протестировано и работает:)