good_evening - 1 year ago 75
PHP Question

# Php recursion to get all possibilities of strings

Here is my code to get all possibilities:

``````\$seq[1] = 'd';
\$seq[2] = 'f';
\$seq[3] = 'w';
\$seq[4] = 's';

for(\$i = 1; \$i < 5; \$i++)
{
\$s['length_1'][] = \$seq[\$i];
\$c1++;

for(\$i2 = \$i+1; \$i2 < 5; \$i2++)
{
\$s['length_2'][] = \$seq[\$i].\$seq[\$i2];
\$last = \$seq[\$i].\$seq[\$i2];
\$c2++;

for(\$i3 = \$i2+1; \$i3 < 5; \$i3++)
{
\$s['length_3'][] = \$last.\$seq[\$i3];
\$last = \$last.\$seq[\$i3];
\$c3++;

for(\$i4 = \$i3+1; \$i4 < 5; \$i4++)
{
\$s['length_4'][] = \$last.\$seq[\$i4];
\$c4++;
}
}
}
}

for(\$i = 0; \$i < \$c1; \$i++)
echo \$s['length_1'][\$i].'<br>';

for(\$i = 0; \$i < \$c2; \$i++)
echo \$s['length_2'][\$i].'<br>';

for(\$i = 0; \$i < \$c3; \$i++)
echo \$s['length_3'][\$i].'<br>';

for(\$i = 0; \$i < \$c4; \$i++)
echo \$s['length_4'][\$i].'<br>';
``````

But if I want to add more, then I will have to add one more loop. So, how can I do it with recursion? I try, I try, but I really can't do it.

Thank you.

Here's a simple algo. Iterate from 1 to 2count(array)-1. On each iteration, if j-th bit in a binary representation of the loop counter is equal to 1, include j-th element in a combination.

As PHP needs to be able to calculate 2count(array) as an integer, this may never exceed `PHP_INT_MAX`. On a 64-bit PHP installation your array cannot have more than 62 elements, as 262 stays below `PHP_INT_MAX` while 263 exceeds it.

EDIT: This computes all possible combinations, not permutations (ie, 'abc' = 'cba'). It does so by representing the original array in binary and "counting up" from 0 to the binary representation of the full array, effectively building a list of every possible unique combination.

``````\$a = array('a', 'b', 'c', 'd');

\$len  = count(\$a);
\$list = array();

for(\$i = 1; \$i < (1 << \$len); \$i++) {
\$c = '';
for(\$j = 0; \$j < \$len; \$j++)
if(\$i & (1 << \$j))
\$c .= \$a[\$j];
\$list[] = \$c;
}

print_r(\$list);
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download