Link to home
Start Free TrialLog in
Avatar of SSupreme
SSupremeFlag for Belarus

asked on

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

Open in new window


Thanks
Avatar of Robert Schutt
Robert Schutt
Flag of Netherlands image

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

?>

Open in new window

By the way: with 10 elements this will generate a lot of output and run for quite some time when executed from a webserver.
ASKER CERTIFIED SOLUTION
Avatar of Ray Paseur
Ray Paseur
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of SSupreme

ASKER

Thanks for reply.
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
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Ray, you missed understand me.
Your code's output like:
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

How to adopt your code to output in same manner?
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++;
	}
}

?>

Open in new window

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) {

Open in new window

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
// ADAPTED FROM http://cogo.wordpress.com/2008/01/08/string-permutation-in-php/
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);

Open in new window

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
Ray, I haven't seen you last solution, but it works as I said:
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.
Ray, you made my day! Thanks a lot!

p.s. I didn't want to offend anyone with points. Good job both of you.