good_evening - 1 year ago 59

PHP Question

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.

Please help and post example as simple as possible.

Thank you.

Answer Source

Here's a simple algo. Iterate from 1 to 2^{count(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 2^{count(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 2^{62} stays below `PHP_INT_MAX`

while 2^{63} 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);
```