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

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 )
        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 2

Рекурсия.

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

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

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