3

假设您正在使用一种具有可变长度数组的语言（例如 with A[i]for all iin 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']

这有时被称为中文菜单问题，并且 for fixedn可以很简单地编码（例如 for 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 语句，我用一个更简单的解决方案替换了它。但我不确定这是重构它的最佳（当然也不是唯一）方法。

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

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

Teaser：我试图推销递归解决方案，但他们不接受，所以我不得不坚持在 HLL 中编写 fortran。

我选择的答案，发布在下面。

4

3 回答 3

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

或者与优化的尾部调用相同，使用数组作为索引，并增加最后一个索引直到它达到相应数组的长度，然后向上进行增量。

于 2009-03-18T17:00:18.350 回答
1

递归。

或者，更好的是，尝试使用类似堆栈的结构和 while 语句来消除递归。

对于您所说的问题（调用带有可变参数的函数），它完全取决于您正在编码的编程语言；其中许多允许传递可变参数。

于 2009-03-18T16:55:42.353 回答
0

因为他们反对递归（不要问），而我反对凌乱的案例陈述（事实证明，这是隐藏了一个错误），所以我选择了这个：

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 个组合，它们还有其他问题），不是递归的，也没有错误。

于 2009-03-20T17:50:35.897 回答