Page 1 of 1

Return combination of all values in an array..

Posted: Sat Sep 23, 2006 7:07 pm
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?

Posted: Sat Sep 23, 2006 8:32 pm
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
 */

Posted: Sat Sep 23, 2006 8:46 pm
by Benjamin
Yeah that is correct.

Posted: Sat Sep 23, 2006 9:15 pm
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.

Posted: Sat Sep 23, 2006 9:18 pm
by Benjamin
Yeah I really appreciate the help, that is a bit out of my league..

Posted: Sat Sep 23, 2006 10:56 pm
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));

Posted: Sun Sep 24, 2006 12:08 am
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
        )

)

Posted: Sun Sep 24, 2006 4:44 am
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.

Posted: Sun Sep 24, 2006 4:47 am
by Benjamin
Ahh I see. That explains it spitting out ~30,000 combinations with 7 array elements.