如何创建递归函数来列出多级数组的所有组合？

Question

我有一个可以包含任意数量元素的数组。每个元素都包含一个ID和一个名为"options“的数组(也可以包含任意数量的元素)。结构是这样的：

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

我想在这个数组的基础上创建另一个数组。每个键是ID字段+一个“option”数组值，值是下一个元素的数组，然后是下一个元素，依此类推。基本上，它应该按照数组定义的顺序给出上述数组的所有组合(有点像树)：

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

因为数组可以包含任意数量的元素，所以我假设我需要包含某种类型的递归函数。我在递归方面没有太多经验，所以这对我来说是一项相当艰巨的任务。

我可以得到一些关于从哪里开始构建这个递归函数的指针吗？

Answer 1

这是怎么回事？当然，这里面有一个bug，但它的方向是正确的……

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

我不能提供PHP版本，但可以提供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))

这给了我们

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