Algorithm redesign: dynamic nested for-loops

Question

I'm trying to run a function with all possible combinations of its parameters. In Python, I'm running into the limit of 20 nested for-loops. Every post on the 'Net says "You're doing it wrong if you hit that limit." So what's the right way to do it?

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

This runs as I want it to:

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

I know this is horrifying. Don't even ask how long it took to write and debug. But, given that I want to test all combinations, I want the list of parameters and values to be dynamic, and I can't modify the function_to_test, how else could I approach this problem?

Addendum:
Here's what func_str contains for the loop where np=1 (i.e., it's running function_to_test with all combinations of two parameters). Hopefully this will somewhat clarify what's happening in my existing code.

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 )

Solution:
The recursive way, as suggested by @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 )

Indeed recursion is the way to do dynamic amounts of for loops. — thermite, Nov 17 '13 at 00:30
I think you're looking for a `PowerSet`. If you search by that name, you should find a better implementation. — GolezTrol, Nov 17 '13 at 00:30
@DarrenKopp Lots of people suggest recursion, and in the end, it appears to work well in this case. I was looking for more than a one-word answer, though. It's a pretty simple solution once you've seen it, but I'd never seen it. — jab, Nov 17 '13 at 01:54
@DarrenKopp Sorry, it's just that every search I did before posting this question said merely, "Use recursion." So I was really looking for an answer to, "How would I apply recursion to this problem?" But of course you had no way of knowing that. — jab, Nov 17 '13 at 02:02

Sergey Kalinichenko · Accepted Answer · 2013-11-17T00:38:29.863

You can do this recursively or iteratively.

Recursive method requires you to build an array with the cardinality equal to the number of parameters through which you wish to iterate. Each level of recursion is responsible for cycling through parameters at the index that corresponds to the level of recursive invocation. On each iteration the function makes a call of itself with the partially prepared array of parameters. When the last level is reached, the array contains a complete combination.

Here is a skeleton of the recursive algorithm:

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

Top-level call looks like this:

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

An iterative approach requires computing the number of combinations, iterating through combination numbers, and "decoding" the actual combination from its number.

For example, if you have thee arguments - {T, F}, {R, G, B}, and {0, 1}, you compute that the number of combinations is 2 * 3 * 2 = 12, then you iterate 0 through 11, and decode the value as follows:

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.
}

The code OP provided already appears to be doing this recursively, albeit seemingly overcomplicating it a bit (although I'm not a Python expert). — Bernhard Barker, Nov 17 '13 at 00:37
Exactly what I was looking for, thanks. I'm moderately offended at the "not workable" comment, though -- it works correctly and completely for fewer than 10 parameters, before it runs into Python's nesting limit. And I'd argue that Python is far more language-neutral than JavaScript or whatever you posted (and do you seriously use `i != 3` as a for-loop stopping condition??). But as I said, your answer was exactly what I was looking for, and it helped me solve my problem much more cleanly. — jab, Nov 17 '13 at 01:45
@jab I do use `!=` for all my for-loop termination conditions ([here is why I think it's a good idea](http://stackoverflow.com/a/8884617/335858)). — Sergey Kalinichenko, Nov 17 '13 at 01:59
@dasblinkenlight I'd never thought about it that way before. I think I still disagree, but I respect the logic of it. — jab, Nov 17 '13 at 02:04

Algorithm redesign: dynamic nested for-loops

1 Answers1