Каков хороший способ структурировать вложенные циклы переменных?
-
20-08-2019 - |
Вопрос
Предположим, вы работаете на языке с массивами переменной длины (например,с A[i]
для всех i
в 1..A.length
) и должны написать процедуру, которая принимает n
(n : 1..8
) массивы переменной длины элементов в массиве переменной длины длины n
, и ему необходимо вызвать процедуру любой возможной длины n
массив элементов, где первый выбирается из первого массива, второй — из второго массива и т. д.
Если вы хотите визуализировать что-то конкретное, представьте, что ваша программа должна принимать такие данные, как:
[ [ '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']
Иногда это называют проблемой китайского меню. n
можно закодировать довольно просто (например.для n
= 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] )
А вдруг n
может варьироваться, давая подпись типа:
procedure register_combination( items : vararray of vararray of An_item)
Написанный код содержал уродливый оператор case, который я заменил гораздо более простым решением.Но я не уверен, что это лучший (и, конечно, не единственный) способ рефакторинга.
Как бы вы это сделали?Умный и неожиданный — это хорошо, но понятный и удобный в сопровождении — еще лучше: я просто прохожу этот код и не хочу, чтобы мне перезвонили.Кратко, ясно и умный был бы идеален.
Редактировать:Я опубликую свое решение сегодня позже, после того как другие смогут ответить.
Тизер:Я пытался продать рекурсивное решение, но они на это не пошли, поэтому мне пришлось писать на Фортране в HLL.
Ответ, который я дал, опубликован ниже.
Решение 3
Так как они были против рекурсии (не спрашивайте), а я был против грязных заявлений о делах (которые, как оказалось, скрывали ошибка ) Я пошел с этим:
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.
Для вашей проблемы, которую вы указали (вызов функции с переменными аргументами), это полностью зависит от языка программирования, на котором вы пишете код;многие из них позволяют передавать переменные аргументы.