O que é uma boa maneira de estruturar loops aninhados variáveis?
-
20-08-2019 - |
Pergunta
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.
Solução 3
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 .
Outras dicas
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.
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.