How to compute the cartesian power of a range of characters?

Question

I would like to make a function that is able to generate a list of letters and optional numbers using 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;
        }
    }
}

Thanks

example:

 myfunction($include, $length)

usage something like this:

 myfunction('a..z,0..9', 3);

output:

000
001
...
aaa
aab
...
zzz

The output would have every possible combination of the letters, and numbers.

Answer 1

Setting the stage

First, a function that expands strings like "0..9" to "0123456789" using 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;
}

It handles any number of expandable patterns and takes care to preserve their position inside your source string, so for example

expand_pattern('abc0..4def5..9')

will return "abc01234def56789".

Calculating the result all at once

Now that we can do this expansion easily, here's a function that calculates cartesian products given a string of allowed characters and a length:

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

So for example, to get the output described in the question you would do

$options = cartesian(expand_pattern('a..z0..9'), 3);

See it in action (I limited the expansion length to 2 so that the output doesn't explode).

Generating the result on the fly

Since the result set can be extremely large (it grows exponentially with $length), producing it all at once can turn out to be prohibitive. In that case it is possible to rewrite the code so that it returns each value in turn (iterator-style), which has become super easy with PHP 5.5 because of generators:

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.

Answer 2

See this answer for a code that produces all possible combinations: https://stackoverflow.com/a/8567199/1800369

You just need to add the $length parameter to limit the combinations size.

Answer 3

You can use a recursive function

assuming you mean it can be any number of levels deep, you can use a recursive function to generate an array of the permutations e.g.:

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

With the above function, initialize the return variable and call it:

$return = array();
echo implode(foo(range('a', 'z'), $return, 3), "\n");

And you're output will be all three char combinations from aaa, to zzz:

aaa
aab
...
zzy
zzz

The numeric parameter determins how recursive the function is:

$return = array();
echo implode(foo(range('a', 'z'), $return, 1), "\n");
a
b
c
...

Here's a live example.

Answer 4

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

tested and working :)