Comment construire une fonction récursive pour lister toutes les combinaisons d'une matrice à plusieurs niveaux?

Question

J'ai un tableau qui peut contenir n'importe quel nombre d'éléments. Chaque élément contient un ID et un tableau appelé "options" (également avec n'importe quel nombre d'éléments). Voici la 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 
      ); 

Je voudrais créer un autre tableau basé sur celui-ci. Chaque clé est le champ ID + une valeur de tableau 'option', et la valeur est un tableau de l'élément suivant, puis le suivant, et ainsi de suite. Fondamentalement, il devrait me donner toutes les combinaisons des tableaux ci-dessus (un peu comme un arbre), dans l'ordre que le tableau a été défini:

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

Parce que le tableau peut contenir un certain nombre d'éléments, je suppose que je aurait besoin d'inclure un certain type de fonction récursive. Je n'ai pas beaucoup d'expérience en récursivité, donc c'est une tâche assez ardue pour moi. Puis-je obtenir des pointeurs sur la façon de commencer à construire cette fonction récursive?

Answer 1

Hows this? Bien sûr, il y a un bug là-dedans, mais sa va dans la bonne 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

Je ne peux pas fournir un PHP un, mais un Python:

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

Cela donne

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