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

Question

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

Ответ, который я дал, опубликован ниже.

Answer 1

Так как они были против рекурсии (не спрашивайте), а я был против грязных заявлений о делах (которые, как оказалось, скрывали ошибка ) Я пошел с этим:

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

Answer 2

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

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

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

Answer 3

Рекурсия.

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

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