算法重新设计 : dynamic nested for-loops

Question

我正在尝试使用其参数的所有可能组合来运行一个函数。在 Python 中，我遇到了 20 个嵌套 for 循环的限制。 'Net 上的每个帖子都说“如果你达到那个限制，你就做错了。”那么正确的做法是什么？

def function_to_test( **kwargs ):
    print kwargs

parms = {'parameterA': (True, False),
         'parameterB': (True, False),
         'parameterC': (True, False)}

for np in range( len( parms ) ):
    func_str = '\n'
    p0 = -1
    for p in range( np + 1 ):
        func_str += 2*p*' ' + "for p%d in range( p%d + 1, len( parms ) ):\n" % (p + 1, p)
        func_str += (2*p + 1)*' ' + "key%d = parms.keys()[p%d]\n" % (p + 1, p + 1)
        func_str += (2*p + 1)*' ' + "vals%d = parms[key%d]\n\n" % (p + 1, p + 1)
        func_str += (2*p + 1)*' ' + "for use_val%d in vals%d:\n\n" % (p + 1, p + 1)

    func_str += 2*(np + 1)*' ' + "cmd = \"function_to_test("
    for p in range( np + 1 ):
        func_str += "%s=%s"
        if p < np:
            func_str += ", "
    func_str += ')" % ('
    for p in range( np + 1 ):
        func_str += "key%d, use_val%d, " % (p + 1, p + 1)
    func_str += ")\n"

    func_str += 2*(np + 1)*' ' + "exec( cmd )\n\n"

    exec func_str in globals(), locals()

这按我想要的方式运行:

{'parameterA': True}
{'parameterA': False}
{'parameterC': True}
{'parameterC': False}
{'parameterB': True}
{'parameterB': False}
{'parameterA': True, 'parameterC': True}
{'parameterA': True, 'parameterC': False}
{'parameterA': True, 'parameterB': True}
{'parameterA': True, 'parameterB': False}
{'parameterA': False, 'parameterC': True}
{'parameterA': False, 'parameterC': False}
{'parameterA': False, 'parameterB': True}
{'parameterA': False, 'parameterB': False}
{'parameterC': True, 'parameterB': True}
{'parameterC': True, 'parameterB': False}
{'parameterC': False, 'parameterB': True}
{'parameterC': False, 'parameterB': False}
{'parameterA': True, 'parameterC': True, 'parameterB': True}
{'parameterA': True, 'parameterC': True, 'parameterB': False}
{'parameterA': True, 'parameterC': False, 'parameterB': True}
{'parameterA': True, 'parameterC': False, 'parameterB': False}
{'parameterA': False, 'parameterC': True, 'parameterB': True}
{'parameterA': False, 'parameterC': True, 'parameterB': False}
{'parameterA': False, 'parameterC': False, 'parameterB': True}
{'parameterA': False, 'parameterC': False, 'parameterB': False}

我知道这很可怕。更不要问写调试用了多长时间。但是，鉴于我想测试所有组合，我希望参数和值的列表是动态的，而且我不能修改 function_to_test，我还能如何解决这个问题？

附录:
以下是 func_str 包含的循环，其中 np=1(即，它正在运行 function_to_test，其中包含两个参数的所有组合)。希望这会稍微澄清我现有代码中发生的事情。

for p1 in range( p0 + 1, len( parms ) ):
 key1 = parms.keys()[p1]
 vals1 = parms[key1]

 for use_val1 in vals1:

  for p2 in range( p1 + 1, len( parms ) ):
   key2 = parms.keys()[p2]
   vals2 = parms[key2]

   for use_val2 in vals2:

    cmd = "function_to_test(%s=%s, %s=%s)" % (key1, use_val1, key2, use_val2, )
    exec( cmd )

解决方案:
递归方式，如@dasblinkenlight 所建议。

def do_all( myargs, level ):
    if level == len( parms ):
        function_to_test( **myargs )
    else:
        key = parms.keys()[level]
        for v in range( len( parms[key] ) + 1 ):
            if v < len( parms[key] ):
                myargs[key] = parms[key][v]
            else:
                del myargs[key]
            do_all( myargs, level + 1 )

do_all( {}, 0 )

Answer 1

您可以递归或迭代地执行此操作。

递归方法要求您构建一个基数等于您希望迭代的参数数量的数组。每个递归级别负责循环遍历与递归调用级别对应的索引处的参数。在每次迭代中，函数都会使用部分准备好的参数数组调用自身。当到达最后一层时，数组包含一个完整的组合。

这是递归算法的框架:

function do_all(array args[N], int level) {
    if (level == N) {
        // Print the combination, or do something else with args
    } else {
        foreach (var value in possible_values[level]) {
            args[level] = value;
            do_all(args, level+1);
        }
    }
}

顶级调用如下所示:

var args[N];
var level = 0;
do_all(args, level);

迭代方法需要计算组合的数量，遍历组合数字，并从数字中“解码”实际组合。

例如，如果您有参数 - {T, F}、{R, G, B} 和 {0, 1}，你计算组合的数量是 2 * 3 * 2 = 12，然后你迭代 0 到 11，并解码值如下:

var combCounts = {2, 3, 2};
for (int combination = 0 ; combination != 12 ; combination++) {
    int tmp = combination;
    var args[3];
    for (int i = 0 ; i != 3 ; i++) {
        args[i] = possible_values[i][tmp % combCount[i]];
        tmp /= combCount[i];
    }
    // Use the combination here.
}