Using php, I am looking to find a set of unique combinations of a given length, making sure that two identical values are not present in several combinations. For example, if I want to find all unique combinations of three values (returning to combinations of 2 values, if 3 is impossible) with this array:
$array = array( array('1', '2'), array('3', '4'), array('5', '6'), );
One possible set of combinations is 123, 456, 14, 15, 16, 24, 25, 26, 34, 35, 36. Note that each number is always combined once and only once with another number. No duplicate pairs of numbers appear in any combination. Just for the sake of clarity, although 123 and 135 will be unique combinations, only one of them will be returned, as pair 13 occurs in both. The main criteria are that all numbers are ultimately grouped together by a number, but only once.
In the final product, the number of arrays and the number of values will be noticeably greater than in:
$array = array( array('1', '2', '3', '4', '5', '6', '7', '8'), array('9', '10', '11', '12', '13', '14', '15', '16'), array('17', '18', '19', '20', '21', '22', '23', '24'), array('25', '26', '27', '28', '29', '30', '31') );
Any help / code to achieve this would be most appreciated.
UPDATE:
I applied brute force. First, I use the Math_Combinatorics pear pack to create combinations starting from the specified maximum grouping by size and working up to pairs. That way, I can get all possible combinations on repeat to cut out any repeating clusters within groups. This code works, but is extremely heavily used in memory. Generating all combinations for an array of 32 values in groups of 6 uses an excess of 1.5 GB of memory. Is there a better algorithm or approach that will allow me to use large arrays without running out of memory? Here's the current state of the code:
require_once 'Combinatorics.php'; $combinatorics = new Math_Combinatorics; $array = range(1,20,1); $maxgroup = (6); $combinations = $combinatorics->combinations($array, $maxgroup); for($c=$maxgroup-1;$c>1;$c--) { $comb = $combinatorics->combinations($array, $c); $combinations = array_merge($combinations, $comb); $comb = null; } for($j=0;$j<sizeof($combinations);$j++) { for($i=sizeof($combinations)-1;$i>=$j+1;$i--) { $diff = array_intersect($combinations[$j], $combinations[$i]); if(count($diff)>1) { unset($combinations[$i]); } } $combinations = array_values($combinations); } print_r($combinations);