Page 1 of 3
Array/loop puzzle
Posted: Wed Sep 06, 2006 3:30 am
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?
Posted: Wed Sep 06, 2006 4:59 am
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)
);
Posted: Wed Sep 06, 2006 10:41 am
by bokehman
Surely someone must know how to do this.
Posted: Wed Sep 06, 2006 10:47 am
by Luke
if you recall from a previous thread of yours I can't even do basic arithmatic

sorry... wish I could help
Posted: Wed Sep 06, 2006 12:04 pm
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)
Posted: Wed Sep 06, 2006 12:10 pm
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)

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

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
Thanks for the effort though.
I was hoping the question was simple and I was just overlooking the answer.
Posted: Wed Sep 06, 2006 12:39 pm
by n00b Saibot
$temp is not declared anywhere!!! maybe copy-paste error?
Posted: Wed Sep 06, 2006 12:52 pm
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
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>';
?>
Posted: Wed Sep 06, 2006 12:52 pm
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);
Posted: Wed Sep 06, 2006 12:53 pm
by n00b Saibot
heh, beat you to it scottayy

Posted: Wed Sep 06, 2006 12:59 pm
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.
Posted: Wed Sep 06, 2006 1:10 pm
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.

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.

Posted: Wed Sep 06, 2006 1:31 pm
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.
Posted: Wed Sep 06, 2006 2:01 pm
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;
}