Quel est un bon moyen de structurer des boucles imbriquées variables?

Question

Supposons que vous travaillez dans une langue avec des tableaux de longueur variable (par exemple avec A[i] pour tous i en 1..A.length) et doivent écrire une routine qui prend n (n : 1..8) tableaux de longueur variable d'éléments dans un tableau de longueur variable de longueur n, et doit appeler une procédure avec chaque longueur possible n tableau d'éléments où le premier est choisi dans le premier tableau, le second est choisi dans le second tableau, et ainsi de suite.

Si vous voulez quelque chose de concret pour visualiser, imaginez que votre routine doit prendre des données comme:

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

et faire les appels de procédure suivants (dans l'ordre):

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

C'est parfois appelé un problème de menu chinois, et pour n fixe peut être codé tout simplement (par exemple pour n = 3, en 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]) 

Mais si n peut varier, en donnant comme une signature:

procedure register_combination(items : vararray of vararray of An_item) 

Le code comme écrit contenait une déclaration de cas laid, que je remplacée par une solution beaucoup plus simple. Mais je ne suis pas sûr que ce soit le meilleur (et ce n'est certainement pas le seul) moyen de refactoriser cela.

Comment le feriez-vous? Intelligent et surprenant sont bons, mais clair et maintenable sont meilleurs - je suis juste en train de passer ce code et je ne veux pas être rappelé. Concis, clair et intelligent serait idéal.

Editer: Je posterai ma solution plus tard aujourd'hui, après que d'autres aient eu la chance de répondre.

Résumé: J'ai essayé de vendre une solution récursive, mais ils ne voulaient pas y aller, alors j'ai dû m'en tenir à l'écriture fortran dans un HLL.

La réponse que je suis allé avec, posté ci-dessous.

Answer 1

Depuis qu'ils étaient opposés à la récursivité (ne demandez pas) et j'étais opposé à malpropre déclarations de cas (qui, comme il est apparu, se cachaient a bug) J'y suis allé avec ceci:

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) 

Fondamentalement, Je détermine combien de combinaisons il y a, attribue à chacun un nombre, puis boucle le nombre produisant la combinaison correspondante. Pas un nouveau truc, je soupçonne, mais il vaut la peine de le savoir.

Il est plus court, fonctionne pour toute combinaison pratique de longueurs de liste (s'il y a plus de 2^60 combinaisons, il a d'autres problèmes), n'est pas récursif et n'a pas the bug.

Answer 2

Récursivité.

Ou, mieux encore, d'essayer d'éliminer la récursivité en utilisant des structures de type pile et while.

Pour votre problème que vous avez déclaré (appeler une fonction avec des arguments variables), cela dépend entièrement du langage de programmation dans lequel vous codez; beaucoup d'entre eux permettent de passer des arguments variables.

Answer 3

Soit l'algorithme récursif

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 même avec des appels de queue optimisées, en utilisant un tableau pour les indices, et en incrémentant le dernier index jusqu'à ce qu'il atteigne la longueur de la rangée correspondante, transportant ensuite l'incrément en haut