Php recursion to get all possibilities of strings
One algorithm is here,
function getCombinations($base,$n){
$baselen = count($base);
if($baselen == 0){
return;
}
if($n == 1){
$return = array();
foreach($base as $b){
$return[] = array($b);
}
return $return;
}else{
//get one level lower combinations
$oneLevelLower = getCombinations($base,$n-1);
//for every one level lower combinations add one element to them that the last element of a combination is preceeded by the element which follows it in base array if there is none, does not add
$newCombs = array();
foreach($oneLevelLower as $oll){
$lastEl = $oll[$n-2];
$found = false;
foreach($base as $key => $b){
if($b == $lastEl){
$found = true;
continue;
//last element found
}
if($found == true){
//add to combinations with last element
if($key < $baselen){
$tmp = $oll;
$newCombination = array_slice($tmp,0);
$newCombination[]=$b;
$newCombs[] = array_slice($newCombination,0);
}
}
}
}
}
return $newCombs;
}
I know it is not efficent in any way, but using in small sets should not be a problem
first base parameter is an array containing elements to be considered when generating combinations.
for simple usage and output:
var_dump(getCombinations(array("a","b","c","d"),2));
and output is
array
0 =>
array
0 => string 'a' (length=1)
1 => string 'b' (length=1)
1 =>
array
0 => string 'a' (length=1)
1 => string 'c' (length=1)
2 =>
array
0 => string 'a' (length=1)
1 => string 'd' (length=1)
3 =>
array
0 => string 'b' (length=1)
1 => string 'c' (length=1)
4 =>
array
0 => string 'b' (length=1)
1 => string 'd' (length=1)
5 =>
array
0 => string 'c' (length=1)
1 => string 'd' (length=1)
To list all subsets of an array, using this combinations algorithm just execute
$base =array("a","b","c","d");
for($i = 1; $i<=4 ;$i++){
$comb = getCombinations($base,$i);
foreach($comb as $c){
echo implode(",",$c)."<br />";
}
}
And output is
a
b
c
d
a,b
a,c
a,d
b,c
b,d
c,d
a,b,c
a,b,d
a,c,d
b,c,d
a,b,c,d
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);
Here it is:
<?php
function combinations($text,$space)
{
// $text is a variable which will contain all the characters/words of which we want to make all the possible combinations
// Let's make an array which will contain all the characters
$characters=explode(",", $text);
$x=count($characters);
$comb = fact($x);
// In this loop we will be creating all the possible combinations of the positions that are there in the array $characters
for ($y=1; $y<= $comb; $y++)
{
$ken = $y-1;
$f = 1;
$a = array();
for($iaz=1; $iaz<=$x; $iaz++)
{
$a[$iaz] = $iaz;
$f = $f*$iaz;
}
for($iaz=1; $iaz<=$x-1; $iaz++)
{
$f = $f/($x+1-$iaz);
$selnum = $iaz+$ken/$f;
$temp = $a[$selnum];
for($jin=$selnum; $jin>=$iaz+1; $jin--)
{
$a[$jin] = $a[$jin-1];
}
$a[$iaz] = $temp;
$ken = $ken%$f;
}
$t=1;
// Let’s start creating a word combination: we have all the necessary positions
$newtext="";
// Here is the while loop that creates the word combination
while ($t<=$x)
{
$newtext.=$characters[$a[$t]-1]."$space";
$t++;
}
$combinations[] = $newtext ;
}
return $combinations;
}
function fact($a){
if ($a==0) return 1;
else return $fact = $a * fact($a-1);
}
$a = combinations("d,f,w,s","");
foreach ($a as $v) {
echo "$v"."\n";
}
?>
Output:
dfws
dfsw
dwfs
dwsf
dsfw
dswf
fdws
fdsw
fwds
fwsd
fsdw
fswd
wdfs
wdsf
wfds
wfsd
wsdf
wsfd
sdfw
sdwf
sfdw
sfwd
swdf
swfd
Also, read this;
You can do this:
function combinations($arr) {
$combinations = array_fill(0, count($arr)+1, array());
$combinations[0] = array('');
for ($i = 0, $n = count($arr); $i < $n; ++$i) {
for ($l = $n-$i; $l > 0; --$l) {
$combinations[$l][] = implode('', array_slice($arr, $i, $l));
}
}
return $combinations;
}
Here’s an example:
$arr = array('d', 'f', 'w', 's');
var_dump(combinations($arr));
This produces the following array:
array(
array(''), // length=0
array('d', 'f', 'w', 's'), // length=1
array('df', 'fw', 'ws'), // length=2
array('dfw', 'fws'), // length=3
array('dfws') // length=4
)
A brief explanation:
For each i with 0 ≤ i < n, get all sub-arrays arr[i,i+l] with each possible length of 0 < l ≤ n - i.