Was ist eine gute Möglichkeit, variable verschachtelte Schleifen zu strukturieren?

Question

Angenommen, Sie arbeiten in einer Sprache mit variabler Länge Arrays (zB mit A[i] für alle i in 1..A.length) und haben eine Routine zu schreiben, die n (n : 1..8) mit variabler Länge Arrays von Elementen in einer variablen Länge Array der Länge n nimmt und soll ein Verfahren mit jedem möglichen Länge n Array von Elementen nennen, wo die ersten von der ersten Anordnung gewählt wird, ist der zweite aus der zweiten Anordnung gewählt, und so weiter.

Wenn Sie etwas Konkretes visualisieren wollen, sich vorstellen, dass Ihre Routinedaten zu übernehmen hat, wie:

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

und die folgenden Prozeduraufrufe (in beliebiger Reihenfolge):

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

Dies wird manchmal als ein chinesisches Menü Problem, und für festen n kann ganz einfach codiert werden (beispielsweise für n = 3, in 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] )

Was aber, wenn n kann variieren, um eine Signatur wie die Aufgabe:

procedure register_combination( items : vararray of vararray of An_item)

Der Code geschrieben enthielt eine hässliche Fall Aussage, die ich mit einer viel einfacheren Lösung ersetzt. Aber ich bin nicht sicher, es ist das beste (und es ist sicherlich nicht der einzige) Weg, dies zu Refactoring.

Wie würden Sie es tun? Clever und überraschend sind gut, aber klar und wartbar sind besser - ich bin durch diesen Code einfach vorbei und wollen nicht bekommen zurückgerufen. Kurz und bündig, klar und klug wäre ideal.

Edit:. Ich werde meine Lösung im Laufe des Tages veröffentlichen, nachdem andere haben eine Chance hatte zu reagieren

Teaser: Ich habe versucht, eine rekursive Lösung zu verkaufen, aber sie würde es nicht gehen, also musste ich zu schreiben Fortran in einem HLL-Stick

.

Die Antwort, die ich mit ging, geschrieben unten.

Answer 1

Da sie auf Rekursion entgegengesetzt waren (nicht fragen) und ich war im Gegensatz Fall Aussagen unordentlich (die, wie sich herausstellte, wurden versteckt ein Bug ) ging ich mit dieser:

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)

Grundsätzlich I herausfinden, wie viele Kombinationen gibt, weisen jeweils eine Anzahl, und dann eine Schleife durch die Anzahl der entsprechende Kombination zu erzeugen. Kein neuer Trick, wie ich vermute, aber ein wissenswert.

Es ist kürzer, arbeitet für eine praktische Kombination von Listenlängen (wenn es mehr als 2 ^ 60 Kombinationen sind, sie haben andere Probleme), ist nicht rekursiv, und muss nicht der Fehler .

Answer 2

Entweder der rekursiven Algorithmus

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

oder das gleiche mit Endaufruf optimiert geführt, unter Verwendung einer Anordnung für die Indizes und die letzten Index inkrementieren, bis sie die Länge des entsprechenden Array erreicht, dann das Inkrement up trägt.

Answer 3

Rekursion.

Oder, noch besser, versuchen Rekursion stapelartigen Strukturen und Statements zu beseitigen.

Für Ihr Problem Sie angegeben (Aufruf einer Funktion mit variablen Argumenten) es hängt ganz von der Programmiersprache Sie Codierung in; viele von ihnen ermöglichen variable Argumente zu übergeben.