All possible combinations in array - recursion?

Question

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.

When you say, the map array is limited to six, then all of your valid examples have more than six... — omar-ali
– omar-ali, Commented Feb 4, 2014 at 15:52
@omar-ali he means that there are only 6 indexes in $map (notice $map is an array) — ɴᴀᴛᴇ ᴅᴇᴠ
– ɴᴀᴛᴇ ᴅᴇᴠ, Commented Feb 4, 2014 at 15:55
Could you add what your end goal is? Maybe you are approaching this incorrectly, what are you actually trying to do? — ɴᴀᴛᴇ ᴅᴇᴠ
– ɴᴀᴛᴇ ᴅᴇᴠ, Commented Feb 4, 2014 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
– Tjeerd Kramer, Commented Feb 4, 2014 at 16:02

luxcem · Accepted Answer · 2014-02-04 16:13:50Z

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.

edited Feb 4, 2014 at 16:13

answered Feb 4, 2014 at 16:08

luxcem

1,85422 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Redsandro · Accepted Answer · 2014-02-04 18:16:26Z

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.

Collectives™ on Stack Overflow

All possible combinations in array - recursion?

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related