¿Cuál es una buena manera de estructurar bucles anidados variables?

Question

Suponga que está trabajando en un idioma con matrices de longitud variable (por ejemplo, con A [i] para todos los i en 1..A.length ) y tiene que escribir una rutina que tome n ( n: 1..8 ) conjuntos de elementos de longitud variable en un conjunto de longitud variable de n , y necesita llamar a un procedimiento con cada conjunto de elementos n de longitud posible donde el primero se elige del primer conjunto, el segundo se elige del segundo conjunto, y así sucesivamente.

Si desea visualizar algo concreto, imagine que su rutina debe tomar datos como:

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

y realice las siguientes llamadas de procedimiento (en cualquier orden):

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

Esto a veces se denomina un problema de menú chino, y para n fijo se puede codificar de manera bastante simple (por ejemplo, para n = 3, en pseudocódigo)

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

Pero, ¿qué pasa si n puede variar, dando una firma como:

procedure register_combination( items : vararray of vararray of An_item)

El código escrito contenía una declaración de caso feo, que reemplacé con una solución mucho más simple. Pero no estoy seguro de que sea la mejor (y seguramente no es la única) forma de refactorizar esto.

¿Cómo lo harías? Inteligente y sorprendente son buenos, pero claro y fácil de mantener son mejores: solo estoy pasando este código y no quiero que me devuelvan la llamada. Conciso, claro y inteligente sería ideal.

Editar: publicaré mi solución más tarde hoy, después de que otros hayan tenido la oportunidad de responder.

Teaser: Traté de vender una solución recursiva, pero no lo hicieron, así que tuve que seguir escribiendo fortran en un HLL.

La respuesta con la que fui, publicada a continuación.

Answer 1

Dado que se oponían a la recursión (no preguntes) y me oponía a las declaraciones de casos desordenadas (que, como resultó, se escondían un error ) Fui con esto:

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)

Básicamente, calculo cuántas combinaciones hay, asigno un número a cada una y luego recorro el número que produce la combinación correspondiente. Sospecho que no es un truco nuevo, pero vale la pena conocerlo.

Es más corto, funciona para cualquier combinación práctica de longitudes de lista (si hay más de 2 ^ 60 combinaciones, tienen otros problemas), no es recursivo y no tiene el error .

Answer 2

Ya sea el algoritmo recursivo

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:] )

o lo mismo con las llamadas de cola optimizadas, utilizando una matriz para los índices e incrementando el último índice hasta que alcance la longitud de la matriz correspondiente, luego llevando el incremento hacia arriba.

Answer 3

Recursión.

O, mejor aún, tratando de eliminar la recursividad utilizando estructuras tipo pila y declaraciones while.

Para su problema que usted indicó (llamando a una función con argumentos variables) depende completamente del lenguaje de programación en el que está codificando; muchos de ellos permiten pasar argumentos variables.