# Cartesian like product

I have a code here, which outputs values from array in different orders.
I want to have up to 10 values, but it means with current code I need 45 comparison statemements in last If statements and  not saying about 36 in 9th and so on.
Is the a way to simplify what I am doing?
``````<?php
\$vars = array("a","b","c","d");

foreach (\$vars as \$valuea)
{
echo "<br />".\$valuea;
foreach (\$vars as \$valueb)
{
if (\$valuea==\$valueb){echo "";} else {
echo "<br />".\$valuea.\$valueb;};
foreach (\$vars as \$valuec)
{
if (\$valuec==\$valueb or \$valuea==\$valueb or \$valuea==\$valuec){echo "";} else {
echo "<br />".\$valuea.\$valueb.\$valuec;
};
foreach (\$vars as \$valued)
{
if (\$valuec==\$valueb or \$valuea==\$valueb or \$valuea==\$valuec or \$valuea==\$valued
or \$valued==\$valuec or \$valueb==\$valued){echo "";} else {
echo "<br />".\$valuea.\$valueb.\$valuec.\$valued;
};
};
};
};

};
?>``````

Thanks
Robert Schutt

What you need is recursion, try this:
``````<?php
\$vars = array("a","b","c","d");

findCombi(array());

function findCombi(\$foundSoFar)
{
global \$vars;
\$found_new = false;
foreach (\$vars as \$valuea)
{
if (!in_array(\$valuea, \$foundSoFar)) {
\$found_new = true;
\$foundSoFar[] = \$valuea;
findCombi(\$foundSoFar);
\$foundSoFar = array_slice(\$foundSoFar, 0, -1);
}
}
if (!\$found_new) { // end of recursion
echo "<br />found combi: " . implode(' / ', \$foundSoFar);
}
}

?>``````
By the way: with 10 elements this will generate a lot of output and run for quite some time when executed from a webserver.
Ray Paseur

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.

As you can see my code outputs each value including single, double, etc.
Your code outputs only combinations of all values, but I quite like it as it saves time on execution with large array.
Yes, I now it might take some time, but it depends from a performance of webserver, right?
And output will be around 80Mb.
Sounds like you want something less like this:
http://en.wikipedia.org/wiki/Permutation

... and more like this?
http://en.wikipedia.org/wiki/Combination
Ok, if you're looking at my code, you could add a maximum depth and call it multiple times ie: for 1 to count(\$vars)

But some of Ray's examples may already have that option?

Ray, your code is superfast, but it displays only 5! values, how can I adopt to display all ( 5!+(4!+3!+2!+1!)x5 )?
Robert, How to add a maximum depth?
SOLUTION

membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.

Ray, you missed understand me.
ABC
ACB
BAC
BCA
CAB
CBA

here 3! - 6 outputs

My code outputs:
A
B
C
AB
AC
BA
BC
CA
CB
ABC
ACB
BAC
BCA
CAB
CBA

here 3!+(2!+1!)x3 - 15 outputs

Robert, How to add a maximum depth?
I can't test this at the moment, I assume the code for 10! is still running, LOL.

something like this (untested):
``````<?php
\$vars = array("a","b","c"); // ,"d","e","f","g","h","i","j"

\$foundtotal = 0;

for(\$maxdepth = 0; \$maxdepth < count(\$vars); \$maxdepth++) {
findCombi(array(), \$maxdepth);
}

echo "<br>found total: ".\$foundtotal;

function findCombi(\$foundSoFar, \$depthLeft)
{
global \$vars, \$foundtotal;
\$found_new = false;
if (\$depth_left >= 0) {
foreach (\$vars as \$valuea)
{
if (!in_array(\$valuea, \$foundSoFar)) {
\$found_new = true;
\$foundSoFar[] = \$valuea;
findCombi(\$foundSoFar, \$depthLeft - 1);
\$foundSoFar = array_slice(\$foundSoFar, 0, -1);
}
}
}
if (!\$found_new) { // end of recursion
echo "<br />found combi: " . implode('', \$foundSoFar);
\$foundtotal++;
}
}

?>``````

It kind of repeat itself atm without separating values where required.
Let me think about this a little bit.  It sounds like you want all possible ordered subsets of the data, where 1 <= length(subset) <= length(data), right?

Yes, I think that your solution might be able to output all subsets until minimum length specified for subset.

P.S. I'll be back in few hours.
regarding my untested code: it works if you correct a spelling mistake on line 16:
``if (\$depthLeft >= 0) {``

Robert, yes you are right, it works.
While I was away I was thinking about it and understood that none of this solutions works for me, even mine. The reason is that when array(string) has equal values, for example:
\$abc = 'ABAD'; // for Ray's solution
\$vars = array("a","b","a","d"); // for ours
It takes each value as unique and as the result duplexes appear in the output.
New requirements aren't met.
There may be a faster or more elegant way to do this, but it seems to test out correctly.  It uses a lot of memory - perhaps putting some of the arrays into \$GLOBALS would reduce memory consumption.
http://www.laprbass.com/RAY_combinations_all_ordered_subsets.php
``````<?php // RAY_combinations_all_ordered_subsets.php
error_reporting(E_ALL);
echo "<pre>";

// PROBLEM: FIND ALL ORDERED SUBSETS OF A CHARACTER SET
// EXAMPLE: IN "ABC" IT MUST FIND "A", "AB", "BA", ETC.

// FUNCTION TO GENERATE THE COMBINATIONS OF CHARACTERS IN A STRING.
// OUTPUT IS AN ARRAY OF COUNT = strlen() FACTORIAL
function string_combinations(\$str)
{
if (strlen(\$str) < 2) return array(\$str);

\$combos = array();
\$endpop = substr(\$str, 1);

// RECURSE
foreach (string_combinations(\$endpop) as \$permutation)
{
\$length = strlen(\$permutation);
for (\$i = 0; \$i <= \$length; \$i++)
{
\$combos[] = substr(\$permutation, 0, \$i) . \$str[0] . substr(\$permutation, \$i);
}
}
return \$combos;
}

// GENERATE THE COMBINATIONS OF ELEMENTS IN A ONE-DIMENSIONAL ARRAY
function array_combinations(\$arr)
{
\$return = array();

// GET THE NUMERIC KEY RANGE OF THE INPUT ARRAY
\$str = implode('', range(0, count(\$arr)-1));

// GET THE KEY COMBINATIONS
\$combos = string_combinations(\$str);

// ITERATE OVER THE COMBINATIONS
foreach (\$combos as \$combo)
{
\$out = array();
while (strlen(\$combo))
{
\$key   = substr(\$combo,0,1);
\$combo = substr(\$combo,1);
\$out[] = \$arr[\$key];
}
\$ndx = implode(NULL, \$out);
\$return[\$ndx] = \$out;
}
return \$return;
}

// DEMONSTRATE THE CODE
\$abc = 'ABCDE';
\$abc = str_split(\$abc);
\$cnt = count(\$abc) - 1;

// GET ALL LARGEST COMBINATIONS IN ARRAY FORMAT
\$out = array_combinations(\$abc);
\$out = array_keys(\$out);

// REDUCE THE STRING LENGTHS TO FIND SMALLER COMBINATIONS
while (\$cnt)
{
foreach (\$out as \$key)
{
\$key = substr(\$key, 0, \$cnt);
\$key = str_split(\$key);
sort(\$key);
\$key = implode(NULL, \$key);
\$new[\$key] = \$key;
}
\$cnt--;
}

// WITH EACH OF THE REDUCED STRINGS, ADD ALL COMBINATIONS
foreach (\$new as \$abc)
{
\$arr = array_combinations(str_split(\$abc));
\$out = array_merge(\$out, array_keys(\$arr));
}

// SHOW THE WORK PRODUCT
sort(\$out);
echo "FOUND " . number_format(count(\$out)) . " COMBINATIONS";
echo PHP_EOL;
print_r(\$out);``````
HTH, ~Ray

Good thinking, thanks a lot!
Thanks for the points.  The solution from Robert_Schutt appears to be correct also.  I wouldn't mind at all if you wanted to share some of the points.

best to all, ~Ray