Return combination of all values in an array..

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Return combination of all values in an array..

Post by Benjamin »

I'm trying to figure out how to do this. I can't seem to get my head around it. Basically, lets say I have an array with 3 values, now keep in mind the array can have a variable number of values, from 1 to 12 or maybe even more.

Code: Select all

$colors = array('red', 'green', 'blue');
Now, what I want the code to do, is create every possible combination of these 3 values in every possible order..

ie:
red green blue
green red blue
blue green red
blue red green etc....

Then I want it to drop one of the array elements and do the same with only 2 array values..
red green
green red

Then add that value back and drop a different one..
blue green
green blue

And so one..
blue red
red blue

So basically, if an array contains 10 values, it would create every possible combination of 10,9,8,7,6,5,4,3 and 2 length values.

Any clue how to create something like this?
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

So before I spend half an hour playing with this you want these combinations from red, green, blue as an example?

Code: Select all

$array = array('red', 'green', 'blue');

/*
 red, green, blue
 red, blue, green
 blue, green, red
 blue, red, green
 green, red, blue
 green, blue, red
 green, blue
 blue, green
 green, red
 red, green
 red, blue
 blue, red
 blue
 green
 red
 */
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Post by Benjamin »

Yeah that is correct.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

Yikes... I can't even figure out the forumla for what the combinations actually are. It's some combination of combinations of you catch my drift... kinda like n! + (n-1)!....

If C is the total number of elements and n is the position in the sequence starting at zero it's mayhaps:

Combinations = C! + ((C-n+1) x (C-n)!) + ... (C-C)!

So for red, green, blue that's 3 values with 15 combinations:

Combinations = 3! + (3 x 2!) + (2 x 1!) + 0!
Combinations = 6 + 6 + 2 + 1 = 15

My maths is awful these days though. I'll have a shot at getting all the combinations out.
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Post by Benjamin »

Yeah I really appreciate the help, that is a bit out of my league..
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

I haven't gotten anything working yet but I'm gonna have to get some sleep cos it's 4:55am 8O

Here's what I have so far. There's a flaw in the condition it needs to recurse. I'll figure it out tomorrow.

Code: Select all

<?php

$array = array('r', 'g', 'b', 'w');

/*
 w, r, g, b
 w, b, g, r
 w, g, b, r
 w, g, r, b
 w, b, r, g
 w, r, b, g
 
 b, w, r, g
 b, w, g, r
 b, g, w, r
 b, g, r, w
 b, r, w, g
 b, r, g, w
 
 r, w, g, b
 r, w, b, g
 r, b, w, g
 r, b, g, w
 r, g, b, w
 r, g, w, b
 
 g, w, r, b
 g, w, b, r
 g, b, r, w
 g, b, w, r
 g, r, w, b
 g, r, b, w
 
 w, r, b
 w, b, r
 r, w, b
 r, b, w
 b, w, r
 b, r, w
 
 r, g, b
 r, b, g
 b, g, r
 b, r, g
 g, b, r
 g, r, b
 
 w, g, b
 w, b, g
 b, w, g
 b, g, w
 g, w, b
 g, b, w
 
 w, r, g
 w, g, r
 g, r, w
 g, w, r
 r, w, g
 r, g, w
 
 w, r
 r, w
 
 w, b
 b, w
 
 w, g
 g, w
 
 r, g
 g, r
 
 r, b
 b, r
 
 g, b
 b, g
 
 r
 w
 b
 g
 */

function factorial($num)
{
	$sign = 1;
	if ($num < 0) $sign = -1;
	$num = abs($num);
	$ret = 1;
	$count = 0;
	for ($count = 0; $count < $num; $count++)
	{
		$ret *= ($num-$count);
	}
	return $ret*$sign;
}

function get_all_combinations($array, $ret = array())
{
	if (empty($ret)) foreach ($array as $v) $ret[] = array($v);
	
	for ($i = 0; $i < factorial(count($array)); $i++)
	{
		if ($i == count($array)) $array = array_reverse($array);
		$x = array_shift($array);
		if (count($array) > 1 && $i <= count($array)) $ret = get_all_combinations($array, $ret);
		array_push($array, $x);
		$ret[] = $array;
	}
	return $ret;
}

print_r(get_all_combinations($array));
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Post by Benjamin »

WOW.. Excellent work. What is the flaw? I have done some testing on it and it appears to be working although the counts seem to jump around a bit. If your going to make it better than by all means have at it otherwise I can work with this.

0,1

Code: Select all

Array
(
    [0] => Array
        (
            [0] => 0
        )

    [1] => Array
        (
            [0] => 1
        )

    [2] => Array
        (
            [0] => 1
            [1] => 0
        )

    [3] => Array
        (
            [0] => 0
            [1] => 1
        )

)
a,b,c

Code: Select all

Array
(
    [0] => Array
        (
            [0] => a
        )

    [1] => Array
        (
            [0] => b
        )

    [2] => Array
        (
            [0] => c
        )

    [3] => Array
        (
            [0] => c
            [1] => b
        )

    [4] => Array
        (
            [0] => b
            [1] => c
        )

    [5] => Array
        (
            [0] => b
            [1] => c
            [2] => a
        )

    [6] => Array
        (
            [0] => a
            [1] => c
        )

    [7] => Array
        (
            [0] => c
            [1] => a
        )

    [8] => Array
        (
            [0] => c
            [1] => a
            [2] => b
        )

    [9] => Array
        (
            [0] => b
            [1] => a
        )

    [10] => Array
        (
            [0] => a
            [1] => b
        )

    [11] => Array
        (
            [0] => a
            [1] => b
            [2] => c
        )

    [12] => Array
        (
            [0] => b
            [1] => a
            [2] => c
        )

    [13] => Array
        (
            [0] => a
            [1] => c
            [2] => b
        )

    [14] => Array
        (
            [0] => c
            [1] => b
            [2] => a
        )

)
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

It breaks once you get past 3 values in the combination and starts throwing out too many combinations (it forgets that it's already done a certain combination in another recursion). It's something to do with this:

Code: Select all

if (count($array) > 1 && $i <= count($array))
It's just about right but that needs changing. I'll figure it out.

Now... the dirty non-logical fix is to array_unique the values but that *won't* work if you wanted this array to come out with 15 combinations too:

Code: Select all

$array = array('red', 'red', 'blue');
Since there *should* be some duplicates there.
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Post by Benjamin »

Ahh I see. That explains it spitting out ~30,000 combinations with 7 array elements.
Post Reply