PHP matrix problem

gatorpower · 03-10-2011, 12:17 PM

So suppose I have the following data set:

------- 1 - 2 - 3 - 4
row 1 = A - D - G - J
row 2 = B - E - H - K
row 3 = C - F - I - L

I am trying to create all possible unique combinations of these letters:

ADGJ, ADGK, ADGL, ADHJ, ADHK, ADHL, ADIJ, ADIK, ADIL, etc. There are 81 such combinations in a '3 x 3 x 3 x 3' matrix. The columns are important and I am trying to write a script that can take into account the addition or subtraction of columns, as well as uneven rows.

I can solve it this way:

PHP Code:


			
$a = array('A','B','C');

$b = array('D','E','F');

$c = array('G','H','I');

$d = array('J','K','L');



for ($i=0;$i<count($a);$i++){

for ($j=0;$j<count($b);$j++){

for ($k=0;$k<count($c);$k++){

for ($l=0;$l<count($d);$l++){



echo $a[$i] . $b[$j] . $c[$k] . $d[$l];



}}}} // loops 81 times

...but that's really inefficient. For starters, it would be hard coded for a set number of loops, in this case 4. It also requires that each array be given its own variable. I needed a way to easily add a new column without needing to assign an entire variable. So I tried setting up something like this:

PHP Code:


			
$a = array(



   0 => array('A','B','C'),

   1 => array('D','E','F'),

   2 => array('G','H','I'),

   3 => array('J','K','L')

);



for ($i=0;$i<count($a);$i++){

   for ($j=0;$j<count($a[$i]);$j++){



      // can't do anything

   }

} // loops only 12 times

Is there a way to get the functionality of the first snippet, while making it relatively simple to add/remove those columns and not hard code the number of loops? Thanks

corp769 · 03-10-2011, 12:54 PM

You could definitely use a while loop, and have a counter for how many variables you have within your array. Just a thought.

Nominal Animal · 03-10-2011, 09:24 PM

Yes. PHP arrays have an internal pointer (AKA cursor) you can use (via reset, current, next, each and others). For example, next will return FALSE when there are no more elements in that array.

Consider this PHP function:

PHP Code:


			
function Combinations($matrix)

{

    /* Verify the argument is an array. */

    if (!is_array($matrix) || count($matrix) < 2)

        return FALSE;



    $result = array();



    /* List of row keys -- so they don't need to be 0, 1, .. N-1 */

    $keys = array_keys(&$matrix);



    /* Make sure rows are arrays, and reset them. */

    foreach ($matrix as &$list)

        if (is_array($list))

            reset(&$list);

        else

            return FALSE;



    /* Main loop. */

    while (TRUE) {



        /* Build a new item. */

        $item = "";

        foreach ($matrix as &$list)

            $item .= current(&$list);



        /* Add to result set. */

        $result[] = $item;



        /* Increase the combination index. */

        $key = count($keys) - 1;

        while (next(&$matrix[$keys[$key]]) === FALSE) {

            reset(&$matrix[$keys[$key]]);

            if (--$key < 0)

                break 2;

        }

    }



    /* Done. */

    return $result;

}

Each combination is first built in the temporary variable $item. The foreach loop (within the while loop) goes thorough each array, appending the value at the current internal pointer of each array, to $item. The constructed combination is then appended to the $result array.

I guess the "Increase the combination index" bit is a bit more complex than usual. The idea is to increase the pointer in the last array. If it goes past the end of the array, increase the previous one, and so on. When the first array goes past the end, we break out of both while loops, using break 2.

Does this answer your question?

graemef · 03-10-2011, 11:13 PM

I don't fully understand your requirements.

You said that you wanted "all possible unique combinations of these letters"

You have 12 letters and are displaying a group of 4. For combinations (where ADGJ and ADJG are considered the same) that would be 12!/(8!4!) = (9*10*11*12)/(2*3*4) = 495 possible combinations.

If the elements can't switch rows, thus you can have ADGJ but not ADGE (E switch with J) then you are looking at the the number of permutations in each row 3! = 6, you are then looking at joining each of these permutations together, which would give you (I think) 6^4 or 1296 variations.

With the above you will find some duplications on individual columns, where column 1 changes but columns two and three might be the same as a previous solution. To fix that you would consider a combination of one from three or 3 combinations from each row. Which is I think what you are trying to do, because that would give you 81 solutions. You have four arrays, for which you want to wish to generate the possible combinations of selecting one from three and then merge the arrays together.

IF that is what you wanted then: The issue doesn't look so much like a combinations problem but a merging problem. Work out how you can merge two array so that you have a list of all the combinations.

[[a], [b], [c]] and [[d], [e], [f]]
becomes
[[a,d], [a,e], [a,f], [b,d], [b,e], [b,f],[c,d], [c,e], [c,f]]

gatorpower · 03-11-2011, 02:19 PM

Quote:

Originally Posted by Nominal Animal

Does this answer your question?

Yes it does! Thank you very much

Quote:

Originally Posted by graemef

You said that you wanted "all possible unique combinations of these letters"

It seems like you understood what I meant by the end. I apologize if I was phrasing it ambiguously.