3

I have a question that goes over my head, hope someone can help. I think it may have to be solved by recursion and/or permutations, but I am not good enough of a (PHP) programmer for that.

$map[] = array("0", "1", "2", "3");
$map[] = array("4", "5", "6", "7");
$map[] = array("8", "9", "10", "11");
$map[] = array("12", "13", "14", "15");
$map[] = array("16", "17", "18", "19");
$map[] = array("20", "21", "22", "23");

The $map array is limited to a max length of "6".

I am looking for a way to make all possible combinations. Here are a few VALID combinations:

Example 1:

$map[] = array("0", "1", "2", "3", "4", "5", "6", "7");
$map[] = array("8", "9", "10", "11");
$map[] = array("12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", );
$map[] = array("23");

Example 2:

$map[] = array("0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23");

Example 3:

$map[] = array("0", "1");
$map[] = array("2", "3", "4", "5", "6", "7", "8");
$map[] = array("9", "10", "11");
$map[] = array("12");
$map[] = array("13", "14", "15", "16", "17", "18", "19", "20");
$map[] = array("21", "22", "23");

The values in each of the map arrays have to be in ascending order, e.g. this example is INVALID:

$map[] = array("0", "1", "4");
$map[] = array("3", "5");
etc...

Hope this can be done.

Tjeerd Kramer
  • 223
  • 1
  • 2
  • 12
  • When you say, the map array is limited to six, then all of your valid examples have more than six... – omar-ali Feb 04 '14 at 15:52
  • @omar-ali The examples are the second dimension of $map. – Teaqu Feb 04 '14 at 15:55
  • @omar-ali he means that there are only 6 indexes in `$map` (notice `$map` is an array) – naththedeveloper Feb 04 '14 at 15:55
  • Could you add what your __end goal__ is? Maybe you are approaching this incorrectly, what are you _actually_ trying to do? – naththedeveloper Feb 04 '14 at 15:56
  • I am trying to find the optimal groups. The values (0, 1, 2, 3, etc) refer to "scores" for a timeframe (0 = 00:00 - 01:00, 1 = 01:00 - 02:00, etc.). I can only group and "sum" these scores in to 6 "blocks" of time. I am trying to find a way which groups, or "blocks" produce the best possible total sum. – Tjeerd Kramer Feb 04 '14 at 16:02
  • refer to this [post](http://stackoverflow.com/a/44097540/6521116) – LF00 May 21 '17 at 13:41

2 Answers2

0

A recursive solution.

<?php
function combination($remaining, $current, $combinations) {
    $e = array_shift($remaining);
    $combinations[$current][] = $e;

    if(empty($remaining)) {
        print_r($combinations);
        return;
    }

    combination($remaining, $current, $combinations);
    // 6 Limit remove for all solutions
    if ($current < 6) {
        combination($remaining, $current + 1, $combinations);
    }
}


$remaining = range(0, 23);

combination($remaining, 0, array());

If you want to store all solutions for [0,23] you're gonna have a bad time.

luxcem
  • 1,807
  • 22
  • 37
0

Since you want ranges of numbers, I simplified the question to a matter of permutations.

Here is a shellscript (that executes from the terminal as a node.js script) that calculates the ranges you want:

#!/usr/bin/env nodejs

// Config
var blocksTotal     = 3;    // 6
var numbersTotal    = 6;    // 24
var perms           = [];   // Permutations

// Start the loop
(function divideHours(numbersToGo, blocksToGo, arr) {

    // What block is this? [1 .. 3]
    var block = blocksTotal - --blocksToGo;

    // Divide numbers
    if (block < blocksTotal)
        for (var hour = 0; hour <= numbersToGo; hour++) {
            if (block == 1) var arr = [];
            arr[block-1] = hour;
            divideHours(numbersToGo-hour, blocksToGo, arr);
        }
    // Last block? Assign rest of numbers
    else {
        perms.push(arr.concat([numbersToGo]));
        console.log(arr.concat([numbersToGo]).toString());
    }
})(numbersTotal, blocksTotal);

Testing with a smaller set of ranges and numbers, you get the following permutations:

0,0,6
0,1,5
0,2,4
0,3,3
0,4,2
0,5,1
0,6,0
1,0,5
1,1,4
1,2,3
1,3,2
1,4,1
1,5,0
2,0,4
2,1,3
2,2,2
2,3,1
2,4,0
3,0,3
3,1,2
3,2,1
3,3,0
4,0,2
4,1,1
4,2,0
5,0,1
5,1,0
6,0,0

Looks about right? Now try the bigger numbers, the resulting array is stored in perms.

If you explicitly want every number mentioned in the array, you can use some counters and math to get that kind of array in stead. E.g.:
3,1,2 -> [1,2,3],[4],[5,6]
2,0,4 -> [1,2],[],[3,4,5,6]

Here is a snippet using 6 blocks and 24 numbers:

...
7,2,2,10,0,3
7,2,2,10,1,2
7,2,2,10,2,1
7,2,2,10,3,0
7,2,2,11,0,2
7,2,2,11,1,1
7,2,2,11,2,0
7,2,2,12,0,1
7,2,2,12,1,0
7,2,2,13,0,0
7,2,3,0,0,12
7,2,3,0,1,11
7,2,3,0,2,10
...

..but this list is endless.

Redsandro
  • 11,060
  • 13
  • 76
  • 106