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

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) 

Код, как написано содержал некрасивый случай заявление, которое я заменил с гораздо более простым решением. Но я не уверен, что это лучший (и это не единственный способ) реорганизовать это.

Как вы это сделаете? Умные и удивительные хорошо, но ясны и удобны в обслуживании - я просто прохожу через этот код и не хочу, чтобы меня перезвонили. Краткий, ясный и умный был бы идеальным.

Редактировать: Я опубликую свое решение позже сегодня, после того, как у других был шанс ответить.

Тизер: Я попытался продать рекурсивное решение, но они не пошли бы на это, поэтому мне пришлось придерживаться написания fortran в HLL.

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

Answer 1

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

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

Answer 2

Рекурсия.

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

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

Answer 3

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

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

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