PHP Given increasing numbers in this order, calculate all possible combinations

Question

the problem is simple, but is giving me a headache, I have for example a 4 numbers array, but I can have up to 20 numbers. Given in the following order:

       [1]  [2]  [4]  [5]

I need to obtain all combinations of this numbers, except numbers can't be permuted, so the order is maintained, I'll give an example of what I'm trying to obtain:

     [1] [ ] [4] [5]
     [1] [2] [ ] [5]
     [ ] [2] [4] [5]
     [ ] [ ] [ ] [5]
     and even
     [ ] [ ] [ ] [ ]

The resulting array will contain sub arrays of the resulting numbers

Update: the empty arrays are optional,

          [1] [4] 

               Or

           [2] [4] [5]

Would be ok also, less complications.

My benchmark results : Sebastian Walker 20 numbers array 124.32486701012 microtime 1048576 results Sumurai8 wonkyPermutations 20 numbers array 38.228344917297 microtime 1048576 results Thank you guys. — ion, Nov 01 '15 at 20:43

score 2 · Answer 1 · edited May 23 '17 at 10:27

Basically, what I did is I took this answer's code to find out all the possible "number is there" / "number is not there" combinations, like the following:

0 0 0 0
1 0 0 0
1 1 0 0
1 1 1 0
1 1 1 1
0 1 0 0
and so on...

Afterwards I applied this to the input arrays contents.

<?php
//First of all, find out all possible combinations of "number is there" and "number is not there"

$input = ["1","2","4","5"];

$empty = " "; //Value to insert if "number is not there"

$length = sizeof($input); //How many numbers are in the array

$combinations = pow(2, $length); //Number of possible 1/0 combinations

$sequence = array();

for($x = 0; $x < $combinations; $x++) {
    $sequence[$x] = str_split(str_pad(decbin($x), $length, 0, STR_PAD_LEFT));
}

//Alright, so now we have to apply these combinations to our $input array
$output = [];


foreach($sequence as $combo){
    $output_combo = [];
    foreach($combo as $key=>$val){
        if ($val == 1){
            //"number is there"
            array_push($output_combo, $input[$key]);
        }else{
            //"number is not there"
            array_push($output_combo, $empty);
        }
    }
    array_push($output, $output_combo);
}

//There you go! The variable $output contains your array.

//Display the array (You can leave this part out...)
foreach($output as $combo){
    foreach($combo as $val){
        echo "[" . $val .  "] ";
    }
    echo "<br>";
}

?>

Check out this PHPFiddle - it works with as many numbers as you want. Just make sure the $empty variable contains the value that you want to have if the number is not there.

Simply click this link and choose "Run": http://phpfiddle.org/main/code/fdtn-u5jv

You consume twice the memory needed to generate this list, but it seems to work. — Sumurai8, Nov 01 '15 at 16:07
You might want to put the code in your answer in case that link will become dead in the future. — Mihai, Nov 01 '15 at 16:12
Thank you guys, can't accept more than 1 answer, i will benchmark and select the best solution. — ion, Nov 01 '15 at 16:21

Sumurai8 · Accepted Answer · 2015-11-02T08:13:57.370

What you want to do can be done quite easily, if you realize that what we want to accomplish is in fact recursive. For each subpart we need to make a choice: We add a space, or we add a number from our list.

function wonkyPermutations( $numbers ) {
  return wonkyPermutationsWithSpaces( Array(), $numbers, count( $numbers ) );
}

function wonkyPermutationsWithSpaces( $prefix, $numbers, $maxlength ) {
  if( $maxlength == 0 ) {
    //We can't add anymore
    return Array( $prefix );
  } else {
    //We have two choices: We either add a space, or we don't.
    $prefix1 = $prefix;
    $prefix1[] = NULL;
    $prefix2 = $prefix;
    $prefix2[] = $numbers[0];
    $suffix1 = wonkyPermutationsWithSpaces( $prefix1, array_slice( $numbers, 1 ), $maxlength - 1 );
    $suffix2 = wonkyPermutationsWithSpaces( $prefix2, array_slice( $numbers, 1 ), $maxlength - 1 );

    return array_merge( $suffix1, $suffix2 );
  }
}

$a = Array( 1, 2, 3, 4 );
var_dump( wonkyPermutations( $a ) );

Yup, I somehow mis-interpreted the question. The main gist of the answer is the same though. You'll just need to add `array_slice( ... )` at the other suffix, and you can remove one of the edge cases. — Sumurai8, Nov 02 '15 at 08:15

PHP Given increasing numbers in this order, calculate all possible combinations

2 Answers2