Какой хороший способ структурировать переменные вложенные циклы?

Предположим, вы работаете на языке с массивами переменной длины (например, с 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.

Ответ, с которым я пошел, размещен ниже.


refactoring nested-loops coding-style language-agnostic
person MarkusQ    schedule 18.03.2009    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Либо рекурсивный алгоритм

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

или то же самое с оптимизированными хвостовыми вызовами, используя массив для индексов и увеличивая последний индекс до тех пор, пока он не достигнет длины соответствующего массива, а затем перенося приращение вверх.

person Pete Kirkham    schedule 18.03.2009

arrow_upward
1
arrow_downward

Рекурсия.

Или, что еще лучше, попытаться устранить рекурсию с помощью стекоподобных структур и операторов while.

Для вашей проблемы, которую вы указали (вызов функции с переменными аргументами), это полностью зависит от языка программирования, на котором вы кодируете; многие из них позволяют передавать переменные аргументы.

person Seb    schedule 18.03.2009

arrow_upward
0
arrow_downward

Поскольку они были против рекурсии (не спрашивайте), а я был против беспорядочных операторов 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, у них есть другие проблемы), не является рекурсивным и не имеет ошибка.

person MarkusQ    schedule 20.03.2009
comment
я не понимаю, почему это не рекурсия... вы вызываете register_combination() из register_combination(), верно?? - person Shane N; 17.02.2011