从TAOCP“循环形式的多重排列”理解算法中的问题

Question

我无法理解TAOCP第1卷中讨论的一个算法；第1.3.3节将其命名为“算法A”，称为“循环形式的多个排列”，并与下一页中的示例进行了比较。

在第8行和第9行中提到了不清楚的步骤；例如，在上一次迭代之后，“当前”值如何变成"g“，当前值为"d"？

详情请参阅Knuth的“计算机编程艺术第1卷”(第1.3.3节)。它包含了该算法的详细描述。

详细算法：

算法A(循环形式的多重排列).

该算法采用循环的乘积(如(6) )，以不相交循环的乘积形式计算得到的排列。为了简单起见，这里不描述移除单例循环；这将是算法的一个相当简单的扩展。在执行此算法时，我们依次“标记”输入公式的元素；也就是说，我们以某种方式标记已处理的输入公式中的符号。

• A1。第一关。标记所有左括号，并将每个右括号替换为其匹配的左括号后面的元素的标记副本。(见表1中的示例)
• A2。打开。从左到右搜索，找到输入的第一个无标记元素。(如果标记了所有元素，则算法终止。)设置START等于它；输出一个左括号；输出元素；并标记它。
• A3。见电流。设置电流等于公式的下一个元素。
• A4。扫描公式继续向右，直到到达公式的末尾，或者找到一个等于CURRENT的元素；在后一种情况下，标记它并返回到步骤A3。
• A5。电流=开始？如果当前启动，输出电流并返回到步骤A4，再次从公式的左边开始(从而在输出中继续开发一个循环)。
• A6。关。输出一个右括号，然后返回到步骤A2。

Answer 1

在我的书中，第7行具有当前值d，第8行具有当前值g，第9行具有当前值a。因此，我假设您对第7行和第8行之间的转换感到困惑，如下所示：

Row #  After step no.  START  CURRENT  ( a c f g a ( b c d b ( a e d a ( f a d e f ( b g f a e b  Output
  #7        A5           a       d     x x       x x   x   x x     x x x   x     x x           x    d
  #8        A5           a       g     x x       x x   x x x x     x x x   x     x x x         x    g

第8行以第7行中描述的状态开始，并执行步骤A5，该步骤将光标移回列表的开头，然后返回到步骤A4。在这里，执行步骤A4三次：

1. 一直往前走，直到命中一个d；标记d是因为它等于当前；设置当前等于b，因为b在这个特定d之后。
2. 一直往前走，直到碰到另一个b；标记b，因为它等于当前；设置电流等于g，因为g在这个特定b之后。
3. 直到它到达元素的末尾，因为它找不到另一个g。

如果您比较第7行和第8行，可以看到新标记的d和b。特别是，第8行‘S步骤A5中的步骤A5的第二次迭代是导致当前设置为g的原因。