Finding unique array combinations with PHP (permutations)

Posted by on Jun 23, 2011 in Backend | 4 comments

I was developing a website where people would place horse bets and the system should be able to calculate all the possible permutations based on the user selection. That means: finding all the possible combinations in a two dimensional array. I found a couple of functions but none of them would keep the array keys intact. So, I came up with this idea after a few gray hairs.

It is a mix of recursive array iterations. Consider you have an array like this:

$traits = array
(
	'52' => array('Happy', 'Sad', 'Angry', 'Hopeful'),
	'21' => array('Outgoing', 'Introverted'),
	'12' => array('Tall', 'Short', 'Medium'),
	'36' => array('Handsome', 'Plain', 'Ugly')
);

The function should return all the possible combination of traits, exactly like this (keeping the keys intact):

Array
(
    [0] => Array
        (
            [52] => Happy
            [21] => Outgoing
            [12] => Tall
            [36] => Handsome
        )
 
    [1] => Array
        (
            [52] => Happy
            [21] => Outgoing
            [12] => Tall
            [36] => Plain
        )
 
    [2] => Array
        (
            [52] => Happy
            [21] => Outgoing
            [12] => Tall
            [36] => Ugly
        )
 
    [3] => Array
        (
            [52] => Happy
            [21] => Outgoing
            [12] => Short
            [36] => Handsome
        )
 
    [4] => Array
        (
            [52] => Happy
            [21] => Outgoing
            [12] => Short
            [36] => Plain
        )
--- and so on....

So, here is the function:

function permutations(array $array, $inb=false)
{
	switch (count($array)) {
		case 1:
			// Return the array as-is; returning the first item
			// of the array was confusing and unnecessary
			return $array[0];
			break;
		case 0:
			throw new InvalidArgumentException('Requires at least one array');
			break;
	}

	// We 'll need these, as array_shift destroys them
	$keys = array_keys($array);
	
	$a = array_shift($array);
	$k = array_shift($keys); // Get the key that $a had
	$b = permutations($array, 'recursing');
	
	$return = array();
	foreach ($a as $v) {
		if($v)
		{
			foreach ($b as $v2) {
				// array($k => $v) re-associates $v (each item in $a)
				// with the key that $a originally had
				// array_combine re-associates each item in $v2 with
				// the corresponding key it had in the original array
				// Also, using operator+ instead of array_merge
				// allows us to not lose the keys once more
				if($inb == 'recursing')
					$return[] = array_merge(array($v), (array) $v2);
				else
					$return[] = array($k => $v) + array_combine($keys, $v2);
			}
		}
	}

	return $return;
}

$x = permutations($traits);

Currently, it only works with numeric array keys. That’s the solution I needed at the moment and I haven’t really tested it with literal keys. Ideas and comments are always welcome.

Thanks to Jon from Stack Overflow for his suggestions and ideas.

  • Salvador

    It won’t for two dimensional traits; I modified like this and it worked :

    	public function permutations(array $array, $inb=false){
    	    switch (count($array)) {
    	        case 1:
    	            // Return the array as-is; returning the first item
    	            // of the array was confusing and unnecessary
    	            return $array[0];
    	            break;
    	        case 0:
    	            throw new InvalidArgumentException('Requires at least one array');
    	            break;
    	    }
    
    	    // We 'll need these, as array_shift destroys them
    	    $keys = array_keys($array);
    
    	    $a = array_shift($array);
    	    $k = array_shift($keys); // Get the key that $a had
    		
    	    $b = $this->permutations($array, 'recursing');
    
    	    $return = array();
    	    foreach ($a as $v) {
    	        if($v)
    	        {
    	            foreach ($b as $v2) {
    	                // array($k => $v) re-associates $v (each item in $a)
    	                // with the key that $a originally had
    	                // array_combine re-associates each item in $v2 with
    	                // the corresponding key it had in the original array
    	                // Also, using operator+ instead of array_merge
    	                // allows us to not lose the keys once more
    					if (!is_array($v2)) $v2 = array($v2);
    	                if($inb == 'recursing')
    	                    $return[] = array_merge(array($v), (array) $v2);
    	                else
    	                    $return[] = array($k => $v) + array_combine($keys, $v2);
    	            }
    	        }
    	    }
    
    	    return $return;
    	}
    
  • negge

    Thank you for this function, I had the same problem and this was very helpful.

    To make the function work with literal keys (I needed that functionality) just change line 7 to:

    return reset($array);

  • http://webfly.pl/ jacek

    Thx
    I was need it to my tag function :D

  • Bartek

    Thank you very much. It help me alot with my shopping cart.