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
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post by Mordred »

@scottayy (et al) :
Don't mistake permutations and combinations. http://en.wikipedia.org/wiki/Permutatio ... mbinations

@bokehman:
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?
The problem is that if your array contains many items of which to choose three, the number of array elements in your multi-dimensional array will get too large. A workaround to this is to have a callback function which will be called every time a new subset of three is generated. In that way you won't have to keep them all in memory simultaneously, but on the other hand you have a way to call a function for each of them. See array_walk() for an inspiration if you are not familiar with the concept of callbacks.

You still haven't told us why you need all 3-element combinations of an array - maybe there's a totally different approach to your problem which will remove the need of this computationaly heavy stuff altogether?
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

Alright, here's what I got :) It bugged me so I worked till a solution. It's not brute force... but will create some overhead.

Code: Select all

<?php

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

function determine_possibilities($array)
{
	$count = count($array);
	for($i=0;$i<$count;$i++)
	{
		$new[] = $i;
	}

	$all_possibilities = array_2D_permute($new);
	$combos = array();
	foreach($all_possibilities AS $possibility)
	{
		$possibility = array($possibility[0],$possibility[1],$possibility[2]);
		sort($possibility,SORT_NUMERIC);
		if(!in_array($possibility,$combos))
		{
			$combos[] = $possibility;
		}
	}
	
	return $combos;
}

function return_all_combos_of_three($array)
{
	$combos = determine_possibilities($array);
	foreach($combos AS $combo)
	{
		$new_combo = array();
		foreach($combo AS $v)
		{
			$new_combo[] = $array[$v];
		}
	
		$all_combos[] = $new_combo;
	}
	return $all_combos;
}
?>
Test Code:

Code: Select all

$test_array = array('zero','one','two','three','four');

echo '<pre>';
print_r(return_all_combos_of_three($test_array));
echo '</pre>';
Results:

Code: Select all

Array
(
    [0] => Array
        (
            [0] => zero
            [1] => one
            [2] => two
        )

    [1] => Array
        (
            [0] => zero
            [1] => one
            [2] => three
        )

    [2] => Array
        (
            [0] => zero
            [1] => two
            [2] => three
        )

    [3] => Array
        (
            [0] => one
            [1] => two
            [2] => three
        )

    [4] => Array
        (
            [0] => zero
            [1] => one
            [2] => four
        )

    [5] => Array
        (
            [0] => zero
            [1] => two
            [2] => four
        )

    [6] => Array
        (
            [0] => one
            [1] => two
            [2] => four
        )

    [7] => Array
        (
            [0] => zero
            [1] => three
            [2] => four
        )

    [8] => Array
        (
            [0] => one
            [1] => three
            [2] => four
        )

    [9] => Array
        (
            [0] => two
            [1] => three
            [2] => four
        )

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

errrmmm... will someone confirm I was right or wrong :? I am now getting confused over all this...
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post by Mordred »

n00b Saibot wrote:errrmmm... will someone confirm I was right or wrong :? I am now getting confused over all this...
Not only correct, but I find your solution best of all given until now.If the input array can have lots of elements, I would use something like this:

Code: Select all

function returnComb($anArr, $fnCallback) 
{ 
 $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[] = $fnCallback($i, $j, $k);  //$fnCallback is the name of a function with three parameters

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

Post by bokehman »

I've had this up all day and now suddenly four replies in a row.

n00b Saibot's function looks the simplest... no recurrsion, but is static and doesn't retain the keys. Sweatje's has no recurrsion, is dynamic and retains the keys.

Thanks everyone.
User avatar
sweatje
Forum Contributor
Posts: 277
Joined: Wed Jun 29, 2005 10:04 pm
Location: Iowa, USA

Post by sweatje »

What if you want all the two element combinations? What about all of the four element combinations from a six element array? I think bokehman had a fixed solution, but was looking for a more flexible one.

BTW, with my prior post:

Code: Select all

foreach(combs_of_size(array('a','b','c','d','e','f'),4) as $combo) echo implode('',$combo),"\n";
produces:

Code: Select all

abcd
abce
abde
acde
bcde
abcf
abdf
acdf
bcdf
abef
acef
bcef
adef
bdef
cdef
User avatar
s.dot
Tranquility In Moderation
Posts: 5001
Joined: Sun Feb 06, 2005 7:18 pm
Location: Indiana

Post by s.dot »

aww, i worked hard on my code :cry:

it was fun though :P :wink:
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 »

n00b Saibot wrote: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>';
?>
Actually I don't understand this at all. It doesnt retain the values of the source array.
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

scottayy wrote:aww, i worked hard on my code :cry:

it was fun though :P :wink:
Aren't those the best questions for learning? Definitely better than "unexpected T_ECHO on line 4".
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post by Mordred »

bokehman wrote:
n00b Saibot wrote: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>';
?>
Actually I don't understand this at all. It doesnt retain the values of the source array.

Yeah, yeah, right, gotta be $anArr[$i] and so on. The algo is what's important, and it's good. Now if we want k-subsets for k other than three you have to take another approach, but the OP wanted specifically three. Good job on noticing the bug though, comes from testing with "beautiful" data like array(0, 1, 2, 3, 4) :) :)
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 »

Mordred wrote:Now if we want k-subsets for k other than three you have to take another approach, but the OP wanted specifically three. Good job on noticing the bug though, comes from testing with "beautiful" data like array(0, 1, 2, 3, 4) :) :)
was only quick stab at what I wud do in such situation.. wasn't meant to be foolproof tho.. i was only provding the logic..,. rest is all your work buddy :)
User avatar
bokehman
Forum Regular
Posts: 509
Joined: Wed May 11, 2005 2:33 am
Location: Alicante (Spain)

Post by bokehman »

sweatje wrote:Pretty brute force
I modified your code slightly so it is all grouped into one self contained function but haven't altered the logic at all. It's great for small arrays but impossible for bigger ones as it times out. How could I do ithe same thing without brute force?

By the way the biggest overhead in this function is array_merge (used to preserve the keys).

Code: Select all

function combs_of_size($input, $size)
{
	$steps = count($input) - $size;
	$list = array($input);
	for($i = 0; $i < $steps; $i++)
	{
		$temp = array();
		foreach($list as $curlist)
		{
			$lessOne = array();
			foreach(array_reverse(array_keys($curlist)) as $key)
			{
				$lessOne[] = array_merge(array_diff($curlist, array($curlist[$key])));
			}
			$temp = array_merge($temp, $lessOne);
		}
		$list = $temp;
	}
	$return = array();
	foreach ($list as $comb)
	{
		if (!in_array($comb, $return))
		{
			$return[] = $comb;
		}
	}
	return $return;
}
User avatar
sweatje
Forum Contributor
Posts: 277
Joined: Wed Jun 29, 2005 10:04 pm
Location: Iowa, USA

Post by sweatje »

How about using n00b Saibot's approach but making it dynamic. You want to be careful around using eval, but in this case, there is no chance for accidental evaluation of user input code because all you are doing is creating the dynamic loops and assigning values from the input array, the input array values are never introduced as part of the code being evaluated:

Code: Select all

function combos_of_size($input, $size) {
	$code = '';
	$cnt = count($input);
	$ret = array();
	$i0 = -1;
	for($i=0;$i<$size;++$i) {
		$k = 'i'.($i+1);
		$code .= 'for ($'.$k.'=$i'.$i.'+1; $'.$k.'< $cnt-'.($size-$i-1).'; ++$'.$k.') ';
	}
	$code .= '$ret[] = array($input[$i'.implode('], $input[$i',range(1,$size)).']);';
	eval($code);
	return $ret;
}
with this code:

Code: Select all

foreach(combos_of_size(
	array('a','b','c','d','e','f','g','h','i','j','k','l','m',
	'n','o','p','q','r','s','t','u','v','w','x','y','z'),
	25) as $combo) echo implode('',$combo),"\n";
took very little time to execute and produced:

Code: Select all

abcdefghijklmnopqrstuvwxy
abcdefghijklmnopqrstuvwxz
abcdefghijklmnopqrstuvwyz
abcdefghijklmnopqrstuvxyz
abcdefghijklmnopqrstuwxyz
abcdefghijklmnopqrstvwxyz
abcdefghijklmnopqrsuvwxyz
abcdefghijklmnopqrtuvwxyz
abcdefghijklmnopqstuvwxyz
abcdefghijklmnoprstuvwxyz
abcdefghijklmnoqrstuvwxyz
abcdefghijklmnpqrstuvwxyz
abcdefghijklmopqrstuvwxyz
abcdefghijklnopqrstuvwxyz
abcdefghijkmnopqrstuvwxyz
abcdefghijlmnopqrstuvwxyz
abcdefghiklmnopqrstuvwxyz
abcdefghjklmnopqrstuvwxyz
abcdefgijklmnopqrstuvwxyz
abcdefhijklmnopqrstuvwxyz
abcdeghijklmnopqrstuvwxyz
abcdfghijklmnopqrstuvwxyz
abcefghijklmnopqrstuvwxyz
abdefghijklmnopqrstuvwxyz
acdefghijklmnopqrstuvwxyz
bcdefghijklmnopqrstuvwxyz

Code: Select all

count(combos_of_size(
		array('a','b','c','d','e','f','g','h','i','j','k','l','m',
		'n','o','p','q','r','s','t','u','v','w','x','y','z'),
		20) )
took only 5.6 seconds (~10x combinations of size 25) and reported 230230 combinations produced.
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 »

very nice approach.... nothing to do with recursion.. very nice
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post by Mordred »

The approach is very good indeed, code generation is very easy and nice in interpreted languages.
What concerns me is the actual implementation -- I really do recommend using a callback function against generating all combinations in a 2d array.

Your 230230 combinations of 20 elements mean something like 4 604 600 bytes + the array overhead = ~5M memory
If you go and just put the result in a foreach() like you did in the first example - whoops, there go another 5M

Iterating through all of them with a callback function will mean that only one array of 20 elements will be kept in memory (or maybe two if you pass it to the callback without a reference) -- i.e. a negligible amount.

Using a high-level language is no excuse for being careless with memory and CPU!
Post Reply