如何计算一系列字符的笛卡尔幂？

Question

我想创建一个能够使用az,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

输出将包含字母和数字的所有可能组合.

Answer 1

搭建舞台

首先，像使用"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;
        }
    }
}

看看它的实际效果。