Page 2 of 3

Posted: Wed Sep 06, 2006 2:05 pm
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?

Posted: Wed Sep 06, 2006 2:15 pm
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
        )

)

Posted: Wed Sep 06, 2006 2:45 pm
by n00b Saibot
errrmmm... will someone confirm I was right or wrong :? I am now getting confused over all this...

Posted: Wed Sep 06, 2006 3:43 pm
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; 
}

Posted: Wed Sep 06, 2006 3:57 pm
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.

Posted: Wed Sep 06, 2006 3:58 pm
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

Posted: Wed Sep 06, 2006 3:59 pm
by s.dot
aww, i worked hard on my code :cry:

it was fun though :P :wink:

Posted: Wed Sep 06, 2006 4:09 pm
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.

Posted: Wed Sep 06, 2006 4:13 pm
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".

Posted: Wed Sep 06, 2006 4:15 pm
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) :) :)

Posted: Wed Sep 06, 2006 4:42 pm
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 :)

Posted: Sat Sep 09, 2006 10:59 am
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;
}

Posted: Sat Sep 09, 2006 2:19 pm
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.

Posted: Sat Sep 09, 2006 4:04 pm
by n00b Saibot
very nice approach.... nothing to do with recursion.. very nice

Posted: Sat Sep 09, 2006 5:33 pm
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!