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?

Answer 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;
}

Answer 2

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']}}

Answer 3

A bit too late... ;)
Here's my code anyway:

function combine($array) {
 $cur = array_shift($array);
 $result = array();

 if(!count($array)) {
  foreach($cur['options'] as $option) {
   $result[] = $cur['id'].'-'.$option;
  }
  return $result;
 }

 foreach($cur['options'] as $option) {
  $result[$cur['id'].'-'.$option] = combine($array);
 }
 return $result;
}