Qual è un buon modo per strutturare i loop nidificati variabili?

Question

Supponi di lavorare in una lingua con matrici di lunghezza variabile (ad es. con A [i] per tutti i in 1..A.length ) e devono scrivere una routine che accetta n ( n: 1..8 ) matrici a lunghezza variabile di elementi in una matrice a lunghezza variabile di lunghezza n e deve chiamare una procedura con ogni possibile lunghezza n array di elementi in cui il primo viene scelto dal primo array, il secondo viene scelto dal secondo array e così via.

Se vuoi visualizzare qualcosa di concreto, immagina che la tua routine debba prendere dati come:

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

ed effettua le seguenti chiamate di procedura (in qualsiasi ordine):

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

Questo a volte viene chiamato un problema di menu cinese e per n fisso può essere codificato in modo abbastanza semplice (ad es. per n = 3, in pseudo codice)

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

Ma cosa succede se n può variare, dando una firma del tipo:

procedure register_combination( items : vararray of vararray of An_item)

Il codice come scritto conteneva una brutta istruzione case, che ho sostituito con una soluzione molto più semplice. Ma non sono sicuro che sia il modo migliore (e sicuramente non l'unico) per riformattare questo.

Come lo faresti? Intelligenti e sorprendenti sono buoni, ma chiari e mantenibili sono migliori: sto solo passando questo codice e non voglio essere richiamato. e intelligenti, concisi, chiari sarebbero l'ideale.

Modifica: pubblicherò la mia soluzione più tardi oggi, dopo che gli altri avranno avuto la possibilità di rispondere.

Teaser: ho provato a vendere una soluzione ricorsiva, ma non ci avrebbero provato, quindi ho dovuto continuare a scrivere fortran in una HLL.

La risposta con cui sono andato, pubblicata di seguito.

Answer 1

Dato che erano contrari alla ricorsione (non chiedere) e io ero contrario alle dichiarazioni disordinate (che, a quanto pare, si nascondevano un bug ) Sono andato con questo:

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)

Fondamentalmente, capisco quante combinazioni ci sono, assegna a ognuna un numero, quindi passa in rassegna il numero producendo la combinazione corrispondente. Non un nuovo trucco, sospetto, ma vale la pena conoscerlo.

È più corto, funziona con qualsiasi combinazione pratica di lunghezze di elenco (se ci sono più di 2 ^ 60 combinazioni, hanno altri problemi), non è ricorsivo e non ha il bug .

Answer 2

O l'algoritmo ricorsivo

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 stesso con le chiamate di coda ottimizzate, usando un array per gli indici e incrementando l'ultimo indice fino a raggiungere la lunghezza dell'array corrispondente, portando quindi l'incremento verso l'alto.

Answer 3

La ricorsione.

O, ancora meglio, cercando di eliminare la ricorsione usando strutture simili a stack e istruzioni while.

Per il tuo problema che hai dichiarato (chiamando una funzione con argomenti variabili) dipende interamente dal linguaggio di programmazione in cui stai codificando; molti di essi consentono il passaggio di argomenti variabili.