Quel est le 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 Un [i] pour tout i dans 1..A.length ) et devez écrire une routine qui prend n ( n: 1..8 ) tableaux de longueur variable, d'éléments dans un tableau de longueur variable, longueur n et doit appeler une procédure avec toutes les longueurs possibles n , où le premier est choisi dans le premier, le second, dans le second, et ainsi de suite.

Si vous souhaitez visualiser quelque chose de concret, imaginez que votre routine prenne des données telles que:

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

et effectuez les appels de procédure suivants (dans n'importe quel ordre):

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

Ceci est parfois appelé un problème de menu chinois, et pour un n fixe, il peut être codé très 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 que se passe-t-il si n peut varier, donnant une signature du type:

procedure register_combination( items : vararray of vararray of An_item)

Le code tel qu’écrit contenait une déclaration de casse laide, que j’ai remplacée par une solution beaucoup plus simple. Mais je ne suis pas sûr que ce soit le meilleur (et ce n'est sûrement pas le seul) moyen de le refactoriser.

Comment le feriez-vous? Clever et surprendre sont bons, mais clairs et faciles à maintenir sont meilleurs - je ne fais que passer à travers ce code et je ne veux pas être rappelé. Concis, clair et intelligent serait idéal.

Edit: je posterai ma solution plus tard dans la journée, après que d'autres personnes auront eu la chance de répondre.

Teaser: J’ai essayé de vendre une solution récursive, mais ils n’y ont pas donné raison. J’ai donc dû rester fidèle à l’écriture manuscrite dans un HLL.

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

Answer 1

Puisqu'ils étaient opposés à la récursion (ne demandez pas) et que j'étais opposé aux déclarations de cas désordonnées (qui, en fin de compte, dissimulaient un bogue ) je 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)

En gros, je calcule le nombre de combinaisons, attribue un numéro à chacune d’elles puis passe en revue le nombre qui produit la combinaison correspondante. Je suppose que ce n’est pas un nouveau tour, 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, ils ont d'autres problèmes), n'est pas récursif et n'a pas le bogue .

Answer 2

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 identique avec des appels de queue optimisés en sortie, en utilisant un tableau pour les index et en incrémentant le dernier index jusqu'à ce qu'il atteigne la longueur du tableau correspondant, puis en augmentant l'incrément.

Answer 3

Récursivité.

Ou, mieux encore, essayez d'éliminer la récursivité à l'aide de structures en forme de pile et d'instructions while.

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