O que é uma boa maneira de estruturar loops aninhados variáveis?

Question

Suponha que você está trabalhando em uma linguagem com matrizes de comprimento variável (por exemplo, com A[i] para todos i em 1..A.length) e tem que escrever uma rotina que leva n (n : 1..8) matrizes de comprimento variável de itens em uma matriz de comprimento variável de n comprimento , e necessidades de chamar um processo com todas as possíveis matriz n comprimento de artigos em que o primeiro é escolhido a partir da primeira matriz, o segundo é escolhido a partir da segunda matriz, e assim por diante.

Se você quiser algo concreto para visualizar, imaginar que sua rotina tem de ter dados como:

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

e faça as seguintes chamadas de procedimento (em qualquer ordem):

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

Esta é às vezes chamado um problema cardápio chinês, e por n fixo pode ser codificado muito simplesmente (por exemplo, para n = 3, em pseudo-có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] )

Mas o que se n pode variar, dando uma assinatura como:

procedure register_combination( items : vararray of vararray of An_item)

O código como escrito continha uma declaração caso feio, que eu substituído por uma solução muito mais simples. Mas eu não tenho certeza que é o melhor (e não é certamente a única) maneira de refatorar isso.

Como você faria isso? Inteligente e surpreendente são bons, mas clara e de fácil manutenção são melhores - estou só de passagem este código e não quer se ligou de volta. Conciso, claro e inteligente seria o ideal.

Edit:. Vou postar minha solução ainda hoje, depois de outros tiveram a chance de responder

Teaser:. Eu tentei vender uma solução recursiva, mas eles não iria para ele, então eu tive que manter a escrita fortran em um HLL

A resposta eu fui com, postado abaixo.

Answer 1

Uma vez que eles se opunham a recursividade (não pergunte) e eu era contra as declarações de caso desarrumado (que, como se viu, estavam escondidos um bug ) eu fui com isto:

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)

Basicamente, eu descobrir quantas combinações existem, atribua a cada uma um número, e em seguida, percorrer o número a produzir a combinação correspondente. Não é um truque novo, eu suspeito, mas vale a pena conhecer.

É mais curto, funciona para qualquer combinação prática de lista comprimentos (se houver mais de 2 ^ 60 combinações, eles têm outros problemas), não é recursiva, e não tem o bug .

Answer 2

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

ou o mesmo com as chamadas cauda optimizados para fora, utilizando uma matriz para os índices, e incrementando o último índice até atingir o comprimento da matriz correspondente, e depois processando o incremento acima.

Answer 3

A recursão.

Ou, ainda melhor, tentando eliminar a recursão usando pilha-como estruturas e enquanto declarações.

Para o seu problema que você disse (chamando uma função com argumentos variáveis) que depende inteiramente da linguagem de programação que você está codificando em; muitos deles permitem a passagem de argumentos variáveis.