What's a good way to structure variable nested

问题:

Suppose you're working in a language with variable length arrays (e.g. with A[i] for all i in 1..A.length) and have to write a routine that takes n (n : 1..8) variable length arrays of items in a variable length array of length n, and needs to call a procedure with every possible length n array of items where the first is chosen from the first array, the second is chosen from the second array, and so forth.

If you want something concrete to visualize, imagine that your routine has to take data like:

[ [ 'top hat', 'bowler', 'derby' ], [ 'bow tie', 'cravat', 'ascot', 'bolo'] ... ['jackboots','galoshes','sneakers','slippers']]

and make the following procedure calls (in any order):

try_on ['top hat', 'bow tie', ... 'jackboots']
try_on ['top hat', 'bow tie', ... 'galoshes']
 :
try_on ['derby','bolo',...'slippers']

This is sometimes called a chinese menu problem, and for fixed n can be coded quite simply (e.g. for n = 3, in pseudo code)

procedure register_combination( items : array [1..3] of vararray of An_item)
    for each i1 from items[1]
        for each i2 from items[2]
            for each i3 from items[3]
                register( [ii,i2,i3] )

But what if n can vary, giving a signature like:

procedure register_combination( items : vararray of vararray of An_item)

The code as written contained an ugly case statement, which I replaced with a much simpler solution. But I'm not sure it's the best (and it's surely not the only) way to refactor this.

How would you do it? Clever and surprising are good, but clear and maintainable are better--I'm just passing through this code and don't want to get called back. Concise, clear and clever would be ideal.

Edit: I'll post my solution later today, after others have had a chance to respond.

Teaser: I tried to sell a recursive solution, but they wouldn't go for it, so I had to stick to writing fortran in a HLL.

The answer I went with, posted below.

回答1:

Either the recursive algorithm

procedure register_combination( items )
        register_combination2( [], items [1:] )

procedure register_combination2( head, items)
    if items == []
        print head
    else
       for i in items[0]
           register_combination2( head ++ i, items [1:] )

or the same with tail calls optimised out, using an array for the indices, and incrementing the last index until it reaches the length of the corresponding array, then carrying the increment up.

回答2:

Recursion.

Or, better yet, trying to eliminate recursion using stack-like structures and while statements.

For your problem you stated (calling a function with variable arguments) it depends entirely on the programming language you're coding in; many of them allow for passing variable arguments.

回答3:

Since they were opposed to recursion (don't ask) and I was opposed to messy case statements (which, as it turned out, were hiding a bug) I went with this:

procedure register_combination( items : vararray of vararray of An_item)
    possible_combinations = 1
    for each item_list in items
        possible_combinations = possible_combinations * item_list.length
    for i from 0 to possible_combinations-1
        index = i
        this_combination = []
        for each item_list in items
            item_from_this_list = index mod item_list.length
            this_combination << item_list[item_from_this_list]
            index = index div item_list.length
        register_combination(this_combination)

Basically, I figure out how many combinations there are, assign each one a number, and then loop through the number producing the corresponding combination. Not a new trick, I suspect, but one worth knowing.

It's shorter, works for any practical combination of list lengths (if there are over 2^60 combinations, they have other problems), isn't recursive, and doesn't have the bug.