logo标签列表

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

phpstringrangecartesian-product
5
我希望能够创建一个函数，该函数可以生成包含 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

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

1
你能更具体地说明你想要实现什么吗？你真的想标记“PHP4”吗？ - Passerby
无论是PHP4还是PHP5，任何代码都可以使用。 - Brad
为了以后的参考，你在这里尝试做的是生成一组字符的笛卡尔幂集。此外，你还想要一个方便的符号来描述这个集合。 - Jon
4个回答
2

铺垫

首先，使用range函数编写一个将字符串如"0..9"扩展为"0123456789"的函数：

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

See it in action.

0

你可以使用递归函数

假设你的意思是它可以有任意多层，你可以使用递归函数来生成排列的数组，例如：

/** 
 * 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
...

这里有一个实时示例。

0
-1
$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>";
        }
    }
}

测试通过，运行正常 :)

哦...你更新了你的问题...这段代码从0到z生成了所有可能的组合.... - kraysak
谢谢，但原问题仍然有可选长度。这个做法和我之前的一样，只是合并了范围，这是我没有想到的！:P - Brad
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接