这个字典条目的笛卡尔积可以使用递归来完成吗？

Question

我正在研究一种简单的方法，以紧凑的方式定义要自动实例化和评估的不同分类实验，以获得针对特定问题的最佳算法和参数组合。下面是使笛卡尔积产生所有可能的参数值组合的代码的特定部分：def unpack_parameters(parameters_list):    parameters = []    for parameter_name, parameter_values in parameters_list.items():        if len(parameters) == 0:            parameters = [{parameter_name: parameter_value} for parameter_value in parameter_values]        else:            parameters = [dict(parameter.items() + {parameter_name: parameter_value}.items())                          for parameter_value in parameter_values for parameter in parameters]    return parameters¿我可以通过使用递归得到相同的结果吗？上面的代码有效并产生了预期的结果。我也知道我可以使用 itertools.product 来获得相同的结果。但这是一个学习是否可以在这里使用递归的问题，而不是它是否是解决特定问题的正确工具（尽管我不介意对此发表评论）。如果有人感兴趣，这里是如何使用此代码的：experiment_definitions = {    'sklearn.tree.DecisionTreeClassifier':        {'criterion': ['entropy', 'gini'],         'min_samples_split': [2, 4, 8, 16, 32, 64]}}classifiers = {}for classifier_class, parameters_list in experiment_definitions.items():    classifiers[classifier_class] = unpack_parameters(parameters_list)要产生这个：{'sklearn.tree.DecisionTreeClassifier': [{'min_samples_split': 2, 'criterion': 'entropy'}, {'min_samples_split': 4, 'criterion': 'entropy'}, {'min_samples_split': 8, 'criterion': 'entropy'}, {'min_samples_split': 16, 'criterion': 'entropy'}, {'min_samples_split': 32, 'criterion': 'entropy'}, {'min_samples_split': 64, 'criterion': 'entropy'}, {'min_samples_split': 2, 'criterion': 'gini'}, {'min_samples_split': 4, 'criterion': 'gini'}, {'min_samples_split': 8, 'criterion': 'gini'}, {'min_samples_split': 16, 'criterion': 'gini'}, {'min_samples_split': 32, 'criterion': 'gini'}, {'min_samples_split': 64, 'criterion': 'gini'}]}

Answer 1

所以诀窍是能够编写一个函数cartesian_product()，该函数将数字列表作为输入并返回索引的笛卡尔积，考虑到数字可能是列表的大小。

例如，如果我们有 2 个大小为 2 和 6 的列表（根据您的示例），则cartesian_product([2, 6])应该生成输出：

[[0, 0], [1, 0], [0, 1], [1, 1], [0, 2], [1, 2], [0, 3], [1, 3], [0, 4], [1, 4], [0, 5], [1, 5]]

def cartesian_product(sizes, start=0):

    if not sizes:

        return []

    if start == len(sizes) - 1:

        return [[i] for i in range(sizes[-1])]

    sub_answer_lists = cartesian_product(sizes, start+1)

    ans = []

    for sub_ans_list in sub_answer_lists:

        for j in range(sizes[start]):

            list_copy = [j]

            list_copy.extend(sub_ans_list)

            ans.append(list_copy)

    return ans

def unpack_parameters(params_dict):

    param_keys = []

    param_lists = []

    for key, lst in params_dict.items():

        param_keys.append(key)

        param_lists.append(lst)

    param_lists_sizes = [len(lst) for lst in param_lists]

    cartesian_product_indices = cartesian_product(param_lists_sizes)

    param_map_list = []

    for indices in cartesian_product_indices:

        param_map = {}

        for i, index in enumerate(indices):

            param_key = param_keys[i]

            param_map[param_key] = param_lists[i][index]

        param_map_list.append(param_map)

    return param_map_list

experiment_definitions = {

    'sklearn.tree.DecisionTreeClassifier':

        {'criterion': ['entropy', 'gini'],

         'min_samples_split': [2, 4, 8, 16, 32, 64]}

}

classifiers = {}

for classifier_class, params_dict in experiment_definitions.items():

    classifiers[classifier_class] = unpack_parameters(params_dict)

print(classifiers)

输出：

{'sklearn.tree.DecisionTreeClassifier': [{'criterion': 'entropy', 'min_samples_split': 2}, {'criterion': 'gini', 'min_samples_split': 2}, {'criterion': 'entropy', 'min_samples_split': 4}, {'criterion': 'gini', 'min_samples_split': 4}, {'criterion': 'entropy', 'min_samples_split': 8}, {'criterion': 'gini', 'min_samples_split': 8}, {'criterion': 'entropy', 'min_samples_split': 16}, {'criterion': 'gini', 'min_samples_split': 16}, {'criterion': 'entropy', 'min_samples_split': 32}, {'criterion': 'gini', 'min_samples_split': 32}, {'criterion': 'entropy', 'min_samples_split': 64}, {'criterion': 'gini', 'min_samples_split': 64}]}

编辑：

使用更少内存的生成器版本：

def cartesian_product(sizes, start=0):

    if not sizes:

        yield []

        return

    if start == len(sizes) - 1:

        for i in range(sizes[-1]):

            yield [i]

        return

    for sub_ans_list in cartesian_product(sizes, start+1):

        for j in range(sizes[start]):

            list_copy = [j]

            list_copy.extend(sub_ans_list)

            yield list_copy

Answer 2

是的，像这样：

def product(names, values, current=[])

  pos = len(current)

  if pos >= len(names):

     # a solution

     solutions.append(current.copy())

     return

  for v in values[pos]:

    current.append((names[pos], v)

    product(names, values, current)

    current.pop()