Finding combinations in PHP

June 11, 2007 1:46 PM

How do I find all possible combinations of a multidimensional array in PHP?

This is a pretty simple function that I'm sure many real developers have created in their sleep before me. Unfortunately, I can't find any working examples of their scripts to crib off of.

I'd just like to write a simple function taking a multidimensional array as an argument, and looping through all the possible unique combinations of elements in the array.

Here's a similar question from the archives that includes links to PHP code that's apparently no longer online. Here's an answer to a similar problem that doesn't work in PHP5. There's a solution here that I sorta think I understand, but doesn't seem to work when I execute it. (It produces "PHP Warning: Missing argument 2 for getAllPossiblePermutations()."

Any tips? Thanks in advance!

posted by grrarrgh00 to Computers & Internet (13 answers total)

What does "all combinations" mean? Suppose you're the function and I give you this array. What do you return?

((a, b), (c), (), ((d), e, f, ((g))))
posted by cmiller at 2:11 PM on June 11, 2007

I'm not quite sure what you're looking for either. Do you want to iterate through permutations or combinations? Combinations and permutations are different, mathematically. I'm also not clear how it being a multidimensional array enters into this.
posted by zixyer at 2:36 PM on June 11, 2007

Just a wild guess, but do you want each possible combination of taking one element from each dimension of an array? Like if you ran it on this array:

((a, b), (c, d, e))

The result would be
((a, c), (a, d), (a, e), (b, c), (b, d), (b, e))? That's a really simple algorithm to write.
posted by zixyer at 2:39 PM on June 11, 2007

Yep, zixyer, that's what I want! I read a small bit on the difference between combinations and permutations and I think I want combinations.
posted by grrarrgh00 at 2:51 PM on June 11, 2007

cmiller, I'm not sure exactly what I'd want from that one!

My array includes four other arrays that each contain between two and four items (none of which are arrays). So it looks like this:

((Happy, Sad, Angry, Hopeful), (Outgoing, Introverted), (Tall, Short, Medium), (Handsome, Plain, Ugly))

and I want to return

Happy Outgoing Tall Handsome
Happy Outgoing Short Handsome
Happy Outgoing Medium Handsome
Happy Outgoing Tall Plain
Happy Outgoing Tall Ugly
Happy Outgoing Short Plain ...

... till all the possible unique combinations of traits are accounted for.
posted by grrarrgh00 at 2:57 PM on June 11, 2007

<?php
    header('Content-Type: text/plain');

    function showCombinations($string, $traits, $i)
    {
        if ($i >= count($traits))
            echo trim($string) . "\n";
        else
        {
            foreach ($traits[$i] as $trait)
                showCombinations("$string $trait", $traits, $i + 1);
        }
    }
    
    $traits = array
    (
        array('Happy', 'Sad', 'Angry', 'Hopeful'),
        array('Outgoing', 'Introverted'),
        array('Tall', 'Short', 'Medium'),
        array('Handsome', 'Plain', 'Ugly')
    );
    
    showCombinations(', $traits, 0);
?>
posted by Khalad at 3:21 PM on June 11, 2007

Nuts, Metafilter's post filtering strikes again. That single quote in the call to showCombinations at the end should be two single quotes.
posted by Khalad at 3:22 PM on June 11, 2007

Awesome. Thanks much. Makes plenty of sense.
posted by grrarrgh00 at 3:27 PM on June 11, 2007

Iterations over all combinations of elements in a multidimensional array of predetermined dimensionality is usually just accomplished with a nested loop. In Java this would be :

void printCharacters(char[][][] chars){
    for (int i = 0; i < chars.length; i++){br>
        for (int j = 0; j < chars[i].length; j++){br>
            for (int k = 0; k < chars[i][j].length; k++){br>
                System.out.println(chars[i][j][k]);
            }
        }
    }
}

posted by Netzapper at 3:54 PM on June 11, 2007

Netzapper, FYI, that just iterates over all of the characters in chars once. It doesn't print out all combinations of characters.

To print out combinations simple loops won't suffice. You'll need something that can backtrack. That means either (a) recursion, as I did it, or (b) an iterative solution with a manual stack (or queue). It's similar to how you would traverse a large tree.
posted by Khalad at 5:47 PM on June 11, 2007

Oh, when you say "multidimensional", you mean "exactly two, never more or fewer dimensional". Right?
posted by cmiller at 9:01 AM on June 12, 2007

Yes, cmiller, that's true. I didn't want to call it two-dimensional, because I wasn't sure I'd be using the term accurately, but you are right.
posted by grrarrgh00 at 12:17 PM on June 12, 2007

Actually, two-dimensional, or even multi-dimensional aren't entirely accurate, since the sub-arrays have different size. What you really have is just "an array of arrays", also called a "jagged array".
posted by Khalad at 1:44 PM on June 12, 2007