How to build recursive function to list all combinations of a multi-level array?

Question

I have an array that can contain any number of elements. Each element contains an ID and an array called "options" (also with any number of elements). Here is the structure:

$arr = array(
             array('id' => 10, 'options' => array(3, 5)),
             array('id' => 15, 'options' => array(2, 4, 8, 9)),
             array('id' => 20, 'options' => array(2, 6, 7)),
             // ... any number of elements
            );

I'd like to create another array based off of this one. Each key is the ID field + an 'option' array value, and the value is an array of the next element, and then the next, and so on. Basically it should give me every combination of the above arrays (sort of like a tree), in the order that the array was defined:

$new = array(
             '10-3' => array(
                            '15-2' => array('20-2', '20-6', '20-7'),
                            '15-4' => array('20-2', '20-6', '20-7'),
                            '15-8' => array('20-2', '20-6', '20-7'),
                            '15-9' => array('20-2', '20-6', '20-7')
                            ),
             '10-5' => array(
                            '15-2' => array('20-2', '20-6', '20-7'),
                            '15-4' => array('20-2', '20-6', '20-7'),
                            '15-8' => array('20-2', '20-6', '20-7'),
                            '15-9' => array('20-2', '20-6', '20-7')
                            )
             );

Because the array can contain any number of elements, I'm assuming I would need to include some type of recursive function. I don't have much experience in recursion, so this is a pretty daunting task for me.

Could I get some pointers on where to start in building this recursive function?

score 1 · Accepted Answer · answered Jul 25 '09 at 21:47

1

Hows this ? Sure there's a bug in there, but its going in the right direction ....

function possibilities ($input) {
  $output=array();
  $current = array_shift($input);
  foreach ($current as #key=>$value) {
    if empty($input) {
      $output[] = $key.'-'.$value;
    } else {
      $output[$key.'-'.$value] = possibilities($input);
    }
  }
  return $output;
}

answered Jul 25 '09 at 21:47

benlumley

11,370
2
40
39

Thanks Ben, I really appreciate it! That gives me a good idea on what I need. I'll try it out and let you know. – James Skidmore Jul 25 '09 at 21:54
The logic in your example was pretty much perfect. Thanks again! – James Skidmore Jul 25 '09 at 22:26

score 0 · Answer 2 · answered Jul 25 '09 at 21:55

I can't provide a PHP one, but a Python one:

arr = [ (10, [3,5]),
        (15, [2,4,8,9]),
        (20, [2,6,7]) ]

def combine_options(pair):
    id, options = pair
    res = []
    for i in options:
        res.append("%d-%d" % (id, i))
    return res

def combine(arr, i):
    res = {}
    if i == len(arr)-1:
        return combine_options(arr[i])
    for elem in combine_options(arr[i]):
        res[elem] = combine(arr, i+1)
    return res

import pprint
pprint.pprint(combine(arr,0))

This gives

{'10-3': {'15-2': ['20-2', '20-6', '20-7'],
          '15-4': ['20-2', '20-6', '20-7'],
          '15-8': ['20-2', '20-6', '20-7'],
          '15-9': ['20-2', '20-6', '20-7']},
 '10-5': {'15-2': ['20-2', '20-6', '20-7'],
          '15-4': ['20-2', '20-6', '20-7'],
          '15-8': ['20-2', '20-6', '20-7'],
          '15-9': ['20-2', '20-6', '20-7']}}

Thanks for the extensive example Martin! Too bad I don't know Python :( — James Skidmore, Jul 25 '09 at 22:27

How to build recursive function to list all combinations of a multi-level array?

2 Answers2

Linked