有序遍历的非递归算法
有一系列组合算法，基于以下技术 - 我们观察结构的某些属性，并使用该属性，遍历线性（或接近，无论如何，并不真正重要）时间的所有可能/可访问变体，没有递归。
示例
字典排列 a1 .. a[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] 中的 1 .. a[n]
- 重新平衡 - 在 a[k] = 1 处分配尽可能多的 1尽可能结束，其余设置为零
n的分区（按降序排列）
- 找到第一个k，使得a[k]> a[k + 1]（k = 1 也可以）
- 增加 a[k] = a[k] + 1
- 找到从 k 到最后一个元素的总和，
- 只要总和允许，将左邻居增加 1。
我想，这足以说明此类算法的本质。这些以及其他一些示例可以在优秀的书“算法和编程：问题”中找到和解决方案”。
我的问题如下。请您在任何领域为我描述更多此类算法的示例。如果您还提供算法本身，那就太好了（用语言来说，就像上面那样，更好）。也欢迎参考书籍、文章。也欢迎参考相关的理论问题（例如，我只是不知道什么时候可以构建这样的算法，什么时候不能构建）。
提前致谢。
There is a family of combinatorial algorithms, based on following technique - we observe some property of the structure and, using that property, traversing then all possible/accessible variants in linear (or closed to, whatever, doesn't really matters) time, without recursion.
Examples
lexicographic permutation a1 .. a[n]
- find last a[k] such that a[k] < a[k + 1] > ...
- find the minimal a[m] in a[k + 1] .. a[n] such that a[k] < a[m]
- swap a[m] and a[k]
- revert a[k + 1] .. a[n]
k-subsets of n
- iterate from the end, find first zero, preceded by 1 (first a[k]==0 such that a[k + 1] == 1)
- assign a[k] = 1
- count 1's in a[k] .. a[n]
- rebalance - assign as much 1's at the end as it possible, the rest set to zero
partitions of n (in descending order)
- find first k such that a[k] > a[k + 1] (k = 1 also is ok)
- increase a[k] = a[k] + 1
- find sum of elements from k to the last one
- increase left neighbors by 1 as long as sum allows.
I guess, this is enough to illustrate the nature of such algorithms. These, and some other examples can be found in excellent, superb book "Algorithms and Programming: Problems and Solutions".
My question is following. Can you, please, describe me more examples, in any area, of such algorithms. It would bee great if you also provide the algorithm itself (in words, like above, is preferable). References to the books, articles are also welcome. References to related theoretical issues are also welcome (for example, I just don't have a feeling when such algorithms can be builded and when - not).
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
考虑算法族中的一个算法 A。要么A已经是迭代的，要么如果是递归的，则可以通过显式数据结构模拟调用堆栈，将其转化为等效的迭代算法。请参阅维基百科。
Consider an algorithm A from a family of algorithms. Either A is already iterative, or if it is recursive, it can be transformed into an equivalent iterative algorithm by simulating the calling stack by an explicit data structure. See e.g. Wikipedia.
这与 Jiri 的答案相同，但也许更直接一点：任何可解决的计算问题都可以由图灵机解决，我认为没有人会将图灵机的功能描述为“递归”，而是以国家为基础。换句话说，只要有足够的辅助磁带存储、一个 while 循环和一个 select-case（或等效的分支，例如 if/else 构造），您就可以使用基于状态机的方法解决任何问题 - 包括这些枚举问题。
例如，定义一个基于状态的算法来进行二叉搜索树的中序遍历是相当简单的。
从状态 DL（左下）开始。如果您处于 DL 并且该节点有左子节点，则向下移动到该节点并保持在 DL 状态；否则，打印该节点的内容，如果该节点有右子节点，则更改为状态 DR 并移动到右子节点；如果该节点没有右子节点，则更改为状态 UR 并移动到父节点。
如果处于 DR 状态，并且您有左孩子，请移至左孩子并更改为 DL 状态。否则，如果您有右子节点，则打印该节点的内容并移动到该子节点并保留在 DR 中。否则，移动到父节点并更改为状态 UL。
如果处于状态UR，则打印节点信息，如果有右子节点，则移动到它，并将状态更改为DR； 否则，移动到父节点并保持在 UR。
如果处于状态UL，如果当前节点是其父节点的右子节点，则停留在UL状态并移动到父节点；否则，如果当前节点不是父节点的右子节点，而是左子节点，则更改为状态 UR 并移动到父节点。如果该节点没有父节点，则终止算法。
无论如何，你明白了。有序树遍历本质上是递归的。许多（所有？）其他遍历问题可以用遍历某些树来表达，这里是一种使用状态机在线性时间内进行中序遍历的方法。你认为这个方法的复杂度是O(n)吗？提示：它访问每个节点的次数不超过3次。
This is along the same lines as Jiri's answer, but perhaps a little more direct: any solvable computational problem is solvable by a Turing machine, and I don't think anyone would describe the functioning as a Turing machine as "recursive", but as state-based. In other words, given enough auxiliary tape storage, a while loop and a select-case (or equivalent branching, e.g., if/else, construct), you can solve any problem - including these enumeration problems - using a state-machine based approach.
For instance, it is fairly straightforward to define a state-based algorithm for doing an in-order traversal of a binary search tree.
Begin in state DL (for down-left). If you're in DL and if the node has a left child, move down to it and stay in the state DL; otherwise, print the node's content and if the node has a right child, change to the state DR and move to the right child; if the node has no right child, change to the state UR and move to the parent.
If in the state DR, and you have a left child, move to the left child and change to he state DL. Otherwise, if you have a right child, print the node's contents and move to the child and stay in DR. Otherwise, move to the parent node and change to the state UL.
If in the state UR, print the node information and if there is a right child, move to it and change the state to DR; otherwise, move to the parent and stay in UR.
If in the state UL, if the current node is the right child of its parent, stay in UL and move to the parent; otherwise, if the current node is not a right child of the parent, and it is a left child, change to the state UR and move to the parent. If this node has no parent, terminate the algorithm.
Anyway, you get the idea. Ordered tree traversals are about as inherently recursive as you get; many (all?) other traversal problems can be couched in terms of traversing some tree, and here is a method for doing an inorder traversal in linear time using a state-machine. Do you believe that this method is O(n)? Hint: it visits each node no more than three times.