Array/loop puzzle

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Array/loop puzzle

Post by bokehman »

Code: Select all

$myArray = array(0,1,2,3,4);
for($i = 0, $j = count($myArray); $i < $j; $i++)
{
	foreach($myArray as $k => $v)
	{
		if($i < $k)
		{
			$possibles[] = array_diff($myArray, array($myArray[$i],$myArray[$k]));
		}
	}
}
$myArray can contain three, four or five items. I want to find all possible combinations of three items it is possible to make. At the moment the code works for five items but not for anything else. I want to make the loop dynamic rather than use fixed if else statements as I may want to expand the number of elements in the source array at a later date.

Any ideas?
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

Desired output:

Code: Select all

$input = array(0,1,2);

$output = array(
	array(0,1,2)
);

Code: Select all

$input = array(0,1,2,3);

$output = array(
	array(0,1,2),
	array(0,1,3),
	array(0,2,3),
	array(1,2,3)
);

Code: Select all

$input = array(0,1,2,3,4);

$output = array(
	array(0,1,2),
	array(0,1,3),
	array(0,1,4),
	array(0,2,3),
	array(0,2,4),
	array(0,3,4),
	array(1,2,3),
	array(1,2,4),
	array(1,3,4),
	array(2,3,4)
);
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

Surely someone must know how to do this.
User avatar
Luke
The Ninja Space Mod
Posts: 6424
Joined: Fri Aug 05, 2005 1:53 pm
Location: Paradise, CA

Post by Luke »

if you recall from a previous thread of yours I can't even do basic arithmatic :( sorry... wish I could help
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post by Mordred »

I think that you shouldn't have the need of generating ALL combinations (the number of combinations of n numbers grows pretty fast with n) - why exactly do you need it?

If you need a random one, you can do a random permutation (shuffle() and str_shuffle() work for arrays and strings) and then just use the first 3 elements.

If you really need to walk through all combinations, by all means do NOT generate them in advance in multiple arrays, use a callback while generating them.

(Btw the exact term of what you try to do is "Combinations without repetition", use this to find a better algorithm than the one you're using)
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Post by John Cartwright »

Code: Select all

function returnAllPossibilities($array)
{
   $possibilities = array();
   $count = count($array);

   while (count($possibilities) <= ($count * $count)) 
   {
      shuffle($array);
      
      if (!in_array($temp, $possibilites)) 
      {
         $possibilities[] = $temp;
      }    
   }

   return $possibilities;
}
I can't quite think of a good way to do this.. so I came up with a bad way to (likely going to waste many cycles) :wink:
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

Mordred wrote:If you really need to walk through all combinations, by all means do NOT generate them in advance in multiple arrays, use a callback while generating them.
Maybe I am missing your direction on this but I was going to put them all in one multi dimensional array. What's the problem there?
Jcart wrote:

Code: Select all

function returnAllPossibilities($array)
{
   $possibilities = array();
   $count = count($array);

   while (count($possibilities) <= ($count * $count)) 
   {
      shuffle($array);
      
      if (!in_array($temp, $possibilites)) 
      {
         $possibilities[] = $temp;
      }    
   }

   return $possibilities;
}
I can't quite think of a good way to do this.. so I came up with a bad way to (likely going to waste many cycles) :wink:
That's scary!!! It's worse than brute force!!! I'm not sure where temp is coming from but this line:

Code: Select all

while (count($possibilities) <= ($count * $count))
Max possiblities for count($possibilities) == 10 while ($count * $count) == 25 leaving a loop that looks like this

Code: Select all

while(10 <= 25){
Thanks for the effort though.

I was hoping the question was simple and I was just overlooking the answer.
User avatar
n00b Saibot
DevNet Resident
Posts: 1452
Joined: Fri Dec 24, 2004 2:59 am
Location: Lucknow, UP, India
Contact:

Post by n00b Saibot »

$temp is not declared anywhere!!! maybe copy-paste error?
User avatar
n00b Saibot
DevNet Resident
Posts: 1452
Joined: Fri Dec 24, 2004 2:59 am
Location: Lucknow, UP, India
Contact:

Post by n00b Saibot »

this will work... i don't push it as best solution but should be enough to save you from Jcart's scary monster :lol:

Code: Select all

<?php
function returnComb($anArr)
{
 $retArr = array();
 $Cnt = count($anArr);

 for($i = 0; $i < $Cnt-2; $i++)
  for($j = $i+1; $j < $Cnt-1; $j++)
   for($k = $j+1; $k < $Cnt; $k++)
    $retArr[] = array($i, $j, $k);

 return $retArr;
}

print '<pre>'.print_r(returnComb(array(0, 1, 2, 3, 4)), TRUE).'</pre>';
?>
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

There is a user comment on the shuffle page for doing exactly this (I think).
php.net/shuffle wrote: This is taken from an O'Reilly Book and modified slightly to return all possible permutations of a 1D array:

Code: Select all

# Modified from http://linuxalpha1.eicn.ch/OReilly_books/ books/webprog/pcook/ch04_26.htm 
# Takes a non-associatuve 1D (vector) array of items
#  and returns an array of arrays with each possible permutation
function array_2D_permute($items, $perms = array( )) {
static $permuted_array;
   if (empty($items)) { 
       $permuted_array[]=$perms;
       #print_r($new);
     #print join(' ', $perms) . "\n";
   }  else {
       for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             array_2D_permute($newitems, $newperms);
         }
         return $permuted_array;
   }
}

$arr=array("Architecture","Mexico","Periodicals","Test");
$result=array_2D_permute($arr);
print_r($result);
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
n00b Saibot
DevNet Resident
Posts: 1452
Joined: Fri Dec 24, 2004 2:59 am
Location: Lucknow, UP, India
Contact:

Post by n00b Saibot »

heh, beat you to it scottayy :P
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

scottayy wrote:There is a user comment on the shuffle page for doing exactly this (I think).
That's no good. It produces 120 arrays when it should only produce 10. Thanks anyway.
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

?

An array with 4 elements should produce more than 10 combinations.

0,1,2,3
0,2,1,3
0,3,1,2
0,1,3,2
0,2,3,1
0,3,2,1
1,0,2,3
1,3,2,0
1,2,3,0
1,0,2,3
1,2,0,3

There's more than 10 possible combos off the top of my head. :P Unless I am not understanding your problem.

[edit] Oh, you only want all possible three value combinations. In that case, ignore everything I've said. ;)
Set Search Time - A google chrome extension. When you search only results from the past year (or set time period) are displayed. Helps tremendously when using new technologies to avoid outdated results.
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

scottayy wrote:There's more than 10 possible combos off the top of my head.
You are getting more than ten because you have added order as a consideration.

Put five items in a box and remove two. You will be left with three. That is one combination. The order that PHP lists the items is irrelevant to the fact that there are three items in the box and that amounts one combination.
User avatar
sweatje
Forum Contributor
Posts: 277
Joined: Wed Jun 29, 2005 10:04 pm
Location: Iowa, USA

Post by sweatje »

Pretty brute force, but seems to work:

Code: Select all

function combs_less_one($arr) {
	$ret = array();
	foreach(array_reverse(array_keys($arr)) as $key) {
		$ret[] = array_merge(array_diff($arr, array($arr[$key])));
	}
	return $ret;
}

function combs_of_size($arr, $size) {
	$steps = count($arr)-$size;
	$list = array($arr);
	for($i=0;$i<$steps;++$i) {
		$tmp = array();
		foreach($list as $curlist) {
			$tmp = array_merge($tmp,combs_less_one($curlist));
		}
		$list = $tmp;
	}
	// make unique, array_unique does not work because they are arrays
	$ret = array();
	foreach ($list as $comb) {
		if (!in_array($comb,$ret)) $ret[] = $comb;
	}
	return $ret;
}
Post Reply