CODEWITHSUNDEEP
phparraysmathmultidimensional-array
ion
ion

Reputation: 540

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

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.

Upvotes: 3

Views: 173

Answers (2)

Sebastian Walker
Sebastian Walker

Reputation: 187

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

Upvotes: 2

Sumurai8
Sumurai8

Reputation: 20737

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 ) );

Upvotes: 2

Related Questions