変数のネストされたループを構造化する良い方法は何ですか?
-
20-08-2019 - |
質問
可変長配列(たとえば、A[i]
のすべてのi
に1..A.length
を使用)を使用する言語で作業しており、n
(n : 1..8
)可変長配列を取るルーチンを作成する必要があるとします長さ<=>の可変長配列内の項目で、最初の配列が最初の配列から選択され、2番目が2番目の配列から選択される、可能なすべての長さ<=>項目の配列でプロシージャを呼び出す必要があります。前へ。
具体的に視覚化するものが必要な場合は、ルーチンが次のようなデータを取得する必要があることを想像してください。
[ [ 'top hat', 'bowler', 'derby' ], [ 'bow tie', 'cravat', 'ascot', 'bolo'] ... ['jackboots','galoshes','sneakers','slippers']]
次のプロシージャコールを(任意の順序で)実行します。
try_on ['top hat', 'bow tie', ... 'jackboots']
try_on ['top hat', 'bow tie', ... 'galoshes']
:
try_on ['derby','bolo',...'slippers']
これは中国語メニューの問題と呼ばれることもあり、固定された<=>の場合は非常に簡単にコーディングできます(例:<=> = 3の場合は擬似コード)
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] )
しかし、もし<=>が変化する可能性がある場合、次のような署名を与えます:
procedure register_combination( items : vararray of vararray of An_item)
書かれたコードにはいcase文が含まれていましたが、これをより単純なソリューションに置き換えました。しかし、これがリファクタリングするのに最適な方法であるかどうかはわかりません(確かに唯一ではありません)。
どうしますか?賢くて驚くべきことは良いことですが、明快で保守可能であることはより良いことです。私はこのコードをただ通過しているだけで、コールバックされたくありません。簡潔で明確なと賢いのが理想です。
編集:他の人が応答する機会を得た後、今日、解決策を投稿します。
ティーザー:再帰的なソリューションを販売しようとしましたが、彼らはそれを採用しなかったので、HLLでフォートランを書くことに固執しなければなりませんでした。
一緒に行った回答、以下に掲載。
解決 3
彼らは再帰に反対していたので(尋ねないでください)、私は散らかったcaseステートメントに反対しました(結局のところ、それはバグ)私はこれで行きました:
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)
基本的に、組み合わせの数を把握し、それぞれに番号を割り当ててから、番号をループして対応する組み合わせを生成します。新しいトリックではないのではないかと思いますが、知っておく価値があります。
より短く、リストの長さの実用的な組み合わせで機能し(2 ^ 60を超える組み合わせがある場合、他の問題があります)、再帰的ではなく、バグ。
他のヒント
再帰アルゴリズムのいずれか
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:] )
または末尾呼び出しで最適化され、インデックスに配列を使用し、対応する配列の長さに達するまで最後のインデックスをインクリメントし、インクリメントを繰り上げます。
再帰。
または、さらに良いことに、スタックのような構造とwhileステートメントを使用して再帰を排除しようとします。
あなたが述べた問題(可変引数で関数を呼び出す)については、コーディングしているプログラミング言語に完全に依存します。それらの多くは、可変引数を渡すことができます。