How to split array into all possible combinations

This is the best I can do:

class Combos
{

    /**
     * getPossible then getDivide
     * 
     * @param array $input
     * @return array
     */
    public function getPossibleAndDivided( array $input )
    {
        return $this->getMultiShiftAndDivided( $this->getPossible( $input ) );
    }

    /**
     * return all possible combinations of input
     * 
     * @param array $input
     * @return array
     */
    public function getPossible( array $inputs )
    {
        $result = [];

        if ( count( $inputs ) <= 1 ) {
            $result = $inputs;
        } else {
            $result = array();
            foreach($inputs as $input){

                //make it an array
                $first = [ $input ];  

                //get all inputs not in first
                $remaining = array_diff( $inputs, $first );

                //send the remaining stuff but to ourself
                $combos = $this->getPossible( $remaining );//recursive

                //iterate over the above results (from ourself)
                foreach( $combos as $combo ) {
                    $last = $combo;
                    //convert to array if it's not
                    if( !is_array( $last ) ) $last = [ $last ];
                    //merge them
                    $result[] = array_merge( $first, $last );
                }
            }
        }
        return $result;
    }

    /**
     * shift and divide a multi level array
     *
     * @param array $array
     * @return array
     */
    public function getMultiShiftAndDivided( array $mArray )
    {
        $divided = [];
        foreach ( $mArray as $array ) {
            $divided = array_merge($divided, $this->getShiftAndDivided( $array ));
        }
        return $divided;
    }

    /**
     * shift and divide a single level array
     * 
     * @param array $array
     * @return array
     */
    public function getShiftAndDivided( array $array )
    {        
        $divided = [];
        $array1 = [];
        while( count( $array ) ){
            $array1[] = array_shift( $array );
            $divided[] = [ $array, $array1 ];
        }

        return $divided;
    }
}

How it works

Top level, I don't want to get into all the details. This is basically a 2 step process or at least it was easier to figure it out that way. I built it in a class to keep everything neat. It also allows better unit testing and re-usability.

This requires 2 operations, or at least it was easier for me to do it in 2 instead of as 1. They are combined in this method

public function getPossibleAndDivided( array $input )
{
   return $this->getMultiShiftAndDivided( $this->getPossible( $input ) );
}

This is the main reason I made it a class, to keep everything packaged nicely together. I would call this a wrapper method.

Step One

$Combos->getPossible(array $input)

1. if only one item remains, return $inputs.
   • this is all the combinations it can ever have (its just a single element after all).
2. else It iterates thought $inputs with foreach as $input
   1. Wraps $input as an array named $first
      • this is a single element from $inputs
   2. Gets the remaining elements in $inputs in a non-destructive way as $remaining
      • using array_diff we need both elements as arrays (see aabove)
   3. recursive call to $this->getPossible($remaining) (see #1) and returns as $combos
   4. Iterates over $combos foreach as $combo
      1. $combo is assigned to $last and turned into an array, if its not
         • sometimes combo is an array with several elements
         • sometimes is a single element. It depends on the recursive call
      2. We add to our result set the merger of $first and $last
         • we need both as arrays so we can merge, without causing nesting
3. End Anything in $result is returned.

This basically rotates though all the combinations of the array and returns them in an array like this:

Array
(
    [0] => Array
        (
            [0] => a
            [1] => b
            [2] => c
            [3] => d
            [4] => e
        )

    [1] => Array
        (
            [0] => a
            [1] => b
            [2] => c
            [3] => e
            [4] => d
        )

    [2] => Array
        (
            [0] => a
            [1] => b
            [2] => d
            [3] => c
            [4] => e
        )
 ...
    [117] => Array
        (
            [0] => e
            [1] => d
            [2] => b
            [3] => c
            [4] => a
        )

    [118] => Array
        (
            [0] => e
            [1] => d
            [2] => c
            [3] => a
            [4] => b
        )

    [119] => Array
        (
            [0] => e
            [1] => d
            [2] => c
            [3] => b
            [4] => a
        )

)

Yes it returns 119 results, no I will not include them all.

Step Two

Don't forget the above output is a multi-dimensional array (this is important below).

$Combos->getMultiShiftAndDivided(array $mArray)

This method is intended to be used with multi-dimensional arrays (hence its name). We get this from "Step 1". Its basically a wrapper for $Combos->getShiftAndDivided($array)

1. Iterates over $mArray foreach as $array
2. It calls $this->getShiftAndDivided($array) returns and merges with $divided.
   • there was no need to store the results, so I didn't waste a variable on it.

Output example:

$input = array(array('a','b','c','d','e'));
print_r($combos->getMultiShiftAndDivided($input));

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

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

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

            [1] => Array
                (
                    [0] => a
                    [1] => b
                    [2] => c
                    [3] => d
                    [4] => e
                )

        )

)

$Combos->getShiftAndDivided(array $array)

This method is intended to be used single level arrays.

1. Loops as long as the count of $array is more then 0, while loop
2. $array1 gets the first element from $array added and that element is removed from $array (destructively)
3. we store both $array and $array1 in our results $divided
   • this records there current "state" at that moment
4. when there are no more items in $array we return our results

Output example:

$input = array('a','b','c','d','e');
print_r($combos->getShiftAndDivided($input));

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

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

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

        [1] => Array
            (
                [0] => a
                [1] => b
                [2] => c
                [3] => d
                [4] => e
            )

    )

)

Basically this shifts the elements of a single array to two result arrays and records their state on each shift. I made it 2 functions so that it could be tested easier and be re-used easier.

Another issue is its kind of hard to check for multi-dimensional arrays. I know how to do it, but I didn't feel like it because it's kind of ugly and there is a better way. I say that because its possible to use a one level array in what is getMultiShiftAndDivided and it wouldn't give you what you would expect. Probably you would get an error like this:

//I say probably, but I actually test it ... lol
Warning:  array_shift() expects parameter 1 to be array

Which could be confusing, one could think the code is buggered. So by having the second method call with a type set into it getShiftAndDivided( array $array ). When the wrapping method tries to call this with a string its going to blow up, but in a better way:

Catchable fatal error:  Argument 1 passed to Combos::getShiftAndDivided() must be of the type array, string given

Hopefully that makes sense, it's something I always try to do in cases like this. It just makes life easier in the long run. Both function return the data in the same format, which is convenient (your welcome).

Summary

So the sum of what this does, is find all the combinations of our input, then it takes those and breaks each one into shifted and divided up array. There for it stands to reason that we will have all the possible combinations divided up into 2 arrays anyway possible. Because that is pretty much exactly what I said.

Now I am not 100% it does that, you can check them if you want, it returns like 599 elements at the end. So good luck on that, I would suggest testing just the results of $combos->getPossible($input). If that has all the combinations like it should, then this will have all that it needs. I am not sure if it returns duplicates, I don't think that was specified. But I didn't really check it.

You can call the main method like this:

$input = array('a','b','c','d','e');  
print_r((new Combos)->getPossibleAndDivided($input));

Test It!

P.S. I spell breaks as brakes, but I can write code this, go figure...