什么是结构变量嵌套循环的好方法？ [英] What's a good way to structure variable nested loops?

问题描述

假设您使用可变长度数组的语言（例如 A [i] for all i 1..A.length ），必须编写一个 n （ n：1..8 ）长度为 n 的可变长度数组中的可变长度数组，需要调用每个可能的长度 n 项目数组，其中第一个从第一个数组中选择，第二个从第二个数组中选择，依此类推。

Suppose you're working in a language with variable length arrays (e.g. with A[i] for all i in 1..A.length) and have to write a routine that takes n (n : 1..8) variable length arrays of items in a variable length array of length n, and needs to call a procedure with every possible length n array of items where the first is chosen from the first array, the second is chosen from the second array, and so forth.

如果你想要一些具体的可视化，想象你的例程必须获取如下数据：

If you want something concrete to visualize, imagine that your routine has to take data like:

[ [ 'top hat', 'bowler', 'derby' ], [ 'bow tie', 'cravat', 'ascot', 'bolo'] ... ['jackboots','galoshes','sneakers','slippers']]

order）：

try_on ['top hat', 'bow tie', ... 'jackboots']
try_on ['top hat', 'bow tie', ... 'galoshes']
 :
try_on ['derby','bolo',...'slippers']

这有时称为中文菜单问题，对于固定 n 可以编码相当简单（例如 n = 3，在伪代码中）

This is sometimes called a chinese menu problem, and for fixed n can be coded quite simply (e.g. for n = 3, in pseudo code)

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 可以改变，给出如下签名：

But what if n can vary, giving a signature like:

procedure register_combination( items : vararray of vararray of An_item)

写的代码包含一个丑陋的case语句，替换为更简单的解决方案。但我不确定这是最好的（这当然不是唯一的）重构这种方式。

The code as written contained an ugly case statement, which I replaced with a much simpler solution. But I'm not sure it's the best (and it's surely not the only) way to refactor this.

你会怎么做？聪明和令人惊讶是好的，但清晰和可维护性更好 - 我只是通过这段代码，不想被回调。

How would you do it? Clever and surprising are good, but clear and maintainable are better--I'm just passing through this code and don't want to get called back. Concise, clear and clever would be ideal.

编辑：我会在今天晚些时候发布我的解决方案，之后其他人有机会回应。

I'll post my solution later today, after others have had a chance to respond.

Teaser：我试图卖一个递归的解决方案，但他们不会去，所以我不得不坚持在HLL写fortran。

Teaser: I tried to sell a recursive solution, but they wouldn't go for it, so I had to stick to writing fortran in a HLL.

我的回答如下。

推荐答案

递归（不要问），我反对凌乱的case语句（事实证明，它隐藏了 a bug ）我用这个：

Since they were opposed to recursion (don't ask) and I was opposed to messy case statements (which, as it turned out, were hiding a bug) I went with this:

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)

基本上，我想出了有多少组合，分配一个数字，然后循环通过数字产生相应的组合。

Basically, I figure out how many combinations there are, assign each one a number, and then loop through the number producing the corresponding combination. Not a new trick, I suspect, but one worth knowing.

它更短，适用于任何实际的列表长度组合（如果有超过2 ^ 60种组合，他们有其他问题），不是递归，并且没有错误。

It's shorter, works for any practical combination of list lengths (if there are over 2^60 combinations, they have other problems), isn't recursive, and doesn't have the bug.

这篇关于什么是结构变量嵌套循环的好方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！