algorithm - 有序遍历的非递归算法

Question

有一系列组合算法，基于以下技术 - 我们观察结构的某些属性，然后使用该属性遍历所有可能/可访问的线性变体(或接近，无论如何，并不重要) 时间，没有递归。

例子

字典排列a 1 ..一个[n]

• 找到最后一个 a[k] 使得 a[k] < a[k + 1] > ...
• 在 a[k + 1] .. a[n] 中找到最小的 a[m] 使得 a[k] < a[m]
• 交换a[m]和a[k]
• 还原 a[k + 1] .. a[n]

n 的 k 个子集

• 从末尾开始迭代，找到第一个零，前面是 1(第一个 a[k]==0 使得 a[k + 1] == 1)
• 分配 a[k] = 1
• 计算 a[k] .. a[n] 中的 1
• 重新平衡——在末尾分配尽可能多的 1，其余设置为零

n 的分区(按降序排列)

• 找到第一个 k 使得 a[k] > a[k + 1] (k = 1 也可以)
• 增加 a[k] = a[k] + 1
• 找出从k到最后一个元素的总和
• 在总和允许的情况下，将左邻居增加 1。

我想，这足以说明此类算法的本质。这些以及其他一些示例可以在优秀的书籍“Algorithms and Programming: Problems and Solutions”中找到。

我的问题如下。能否请您在任何领域向我描述此类算法的更多示例。如果您还提供算法本身，那就太好了(换句话说，如上所示，更可取)。也欢迎引用书籍、文章。也欢迎引用相关理论问题(例如，我只是不知道何时可以构建此类算法，何时不能)。

提前致谢。

Answer 1

考虑算法族中的算法 A。要么A已经是可迭代的，要么是递归的，可以通过显式数据结构模拟调用栈，转化为等价的迭代算法。参见例如Wikipedia .