A k-ary tree with n nodes can be encoded as a k-inorder-preorder sequence of length (k−l)n by labelling the tree from 1 to (k−1)n in generalised inorder and then reading off the labelled integers in generalised preorder. The natural ordering of a set of k-ary trees with n nodes is shown to be preserved in the lexico graphic ordering of a set of k-inorder-preorder sequences of length (k−l)n. An efficient algorithm for generating a set of A-inorder-preorder sequences in lexicographic order is presented. This set of A-inorder-preorder sequences can subsequently be converted to the corresponding set of k-ary trees in natural order.

Admissible permutations may be characterised by the absence of certain subsequences in permutations, and may also be characterised by combinations of depth-first traversals of ordered trees. Out of 36 possible combinations, it is shown that there are four essential non-degenerated classes of admissible permutations. The relations between these four classes are established using the inverse, the reverse and the complement mappings. Consequently, any class of admissible permutations can be derived from another class using these mappings. Furthermore, some orderings of admissible permutations are related to the orderings of ordered trees and their binary representations. Such relationships enable any types of the above combinatorial objects to be generated systematically in some orders.

A new formulation for generating all binary trees with n nodes by using tree rotations is presented. Such a new formulation is based on a detailed study of the properties of codewords with (n-1) non-negative integers that are called rotational admissible. A 1 - 1 correspondence between a set of binary trees with n nodes and a set of rotational admissible codewords with (n-1) integers is formally established. As a results, simple and efficient algorithms for generating rotational-admissible codewords and for generating binary trees using rotations are derived. An empirical test reveals that both algorithms run faster than the corresponding Zerling's algorithms for performing the same task.

A one-to-one correspondence between a set of non-regular trees that have ni internal nodes each with ki sons, for 1≤i≤t, and (m+1) leaves and a set of feasible codewords that have ni occurrences of ki, for 1≤i≤t, and m occurrences of 0 is proved to be isotone, where [equation: see PDF] A simple and efficient algorithm for generating a set of non-regular trees in lexicographic order is presented.

A recursive algorithm for generating all partitions of the set {1, 2, …, n} is presented. The average time complexity per partition generated of this algorithm is 𝛉(1.6). This algorithm runs faster than the previously fastest algorithm, whose average time complexity per partition is 𝛉(4). An empirical test confirms that this is indeed the case.

This paper presents an efficient algorithm for solving the Bulterman's reshuffling problem in the spirit of smoothsort. The Bulterman's reshuffling problem is concerned with permuting an array of red and blue elements such that red elements are moved to specified positions without disturbing the relative order of blue elements. This smooth reshuffling algorithm solves the problem by utilising two processes, left sweep and right sweep; the latter is callable from the former. This algorithm is shown to be superior to a previously published algorithm which uses a brute force approach.

This paper presents an implementation of an efficient algorithm for generating all permutations of n marks in a lexicographic order. This algorithm is more efficient than Irving's algorithm in terms of both time and space.

This paper presents three simple and efficient algorithms for generating, ranking and unranking t-ary trees in a lexicographic order. The simplest idea of encoding a t-ary tree with n nodes as a bit-string of length t*n is exploited to its full advantages. It is proved that the lexicographic order in the set of t-ary trees with n nodes is preserved in the set of bit-strings of length t*n, using the above encoding scheme. Thus by generating all bit-strings in the lexicographic order, a simple decoding algorithm can convert them to t-ary trees in the same order. Finally, the theoretical basis for ranking a lexicographic listing of bit-strings is discussed, and the ranking and the unranking algorithms are derived.

A simple programming technique called the termination-indicator technique is introduced. The basic idea is to use variables as termination indicators in multi-exit loops in order to simplify termination conditions of loops. Numerous examples are given illustrating elegant, efficient an structured solutions that benefit from this technique. Comparative results show that the termination-indicator technique is superior and more versatile than other programming techniques using cand/cor, sentinel and state-variables.

A 1-1 mapping between the set of extended ordered trees with n internal nodes and the set of feasible binary bit-patterns with 2n bits is established. By manipulating the feasible bit-patterns, the set of ordered trees with n nodes can be enumerated lexicographically. The ranking and unranking functions are also described. It has been shown that the bit-pattern representation of ordered trees leads to simple construction and easy understanding of the enumerating, ranking and unranking algorithms.

Abstract Fisher advocates that all variables should be made global to programs and subprograms in order to increase the maintainability and to reduce the problems with subprogram linkages, among other things. The fallacies of Fisher's arguments are shown and the advantages and necessity of using local variables are discussed. It is argued that, from a practical point of view, the use of local variables improves the comprehensibility and the time and space efficiency of programs, as well as makes correctness proofs easier and recursion possible.

After the publication of Algorithm 246, Misra [l] suggested an improvement to it.He gave no detailed coding; but from his descriptions, we obtain the following algorithm for generating the binary Gray code of N bits, assuming that A [l . .N] is an array of bits, which is initialized to all 0's.procedure Misral(N: integer); var s, j, i: integer; begin s := 1

The colour Towers of Hanoi problem is proposed. In this variant, discs are coloured white and black. The white and black discs are required to move in the clockwise and the counterclockwise directions, respectively, subject to the usual constraints of the standard problem. Initially, the discs are stacked on the pegs randomly without violating the constraints. The objective is to move them to a specified peg in increasing order with the largest disc at the bottom. A recursive solution to the problem and the unerlying strategies are presented.

In the cyclic Towers of Hanoi problem, all discs are required to move in a clockwise direction only, subject to the usual restrictions of the standard problem. Atkinson, who proposed the modified problem, presented a recursive solution but found it not so easy to solve by iteration. This paper presents an iterative solution to the modified problem using a representation approach. Further, several interesting and intrinsic properties of the cyclic problem are also discussed.

An iterative algorithm for solving the generalized colour Towers of Hanoi problem is presented; and its underlying principles are discussed. The problem is a variant of the Towers of Hanoi problem; it has n black and white discs randomly stacked on three pegs as an initial configuration. The objective is to move all coloured discs to a specified peg subject to the usual constraints of the standard problem; in addition, white and black discs may only move clockwise and counterclockwise, respectively. A comparison with a recursive algorithm for solving the same problem is also made.

An efficient recursive algorithm for generating well-formed parenthesis strings lexicographically is shown. This algorithm can be easily adapted to generate stack-sortable permutations without changing the main control structures of the algorithm. The connection between well-formed parenthesis strings and ordered trees is also illustrated.

A fast algorithm for computing order-k Fibonacci numbers in O(k2 lg n/2k) units of time is presented. Furthermore the time complexity of the algorithm is O((k−1)n) below threshold when n is small and k is large. Finally, the space complexity of this optimal algorithm is better than that of most other reported algorithms for doing the same task.

A new topological sorting algorithm is formulated using the parallel computation approach. The time complexity of this algorithm is of the order of the longest distance between a source node and a sink node in an acyclic digraph representing the partial orderings between elements. An implementation of this algorithm with an SIMD machine is discussed. To avoid contention for logical resources, a synchronization of all processors is proposed and its performance is also discussed.

Abstract When a procedure is activated as a logical last statement in another procedure, optimization could be done to the procedure call and return. Several optimizations are discussed. The first optimization is based on the idea of reusing the current stack frame. With this approach, it is necessary to compute the order of passing parameters. A tactic of computing the dependency of parameters and a heuristic method of breaking the cyclic dependencies are therefore proposed. However, this approach has severe restrictions imposed on the kinds of procedure that can be called; in particular, the called procedure cannot contain references to the calling procedure. To remove all such restrictions, the second and third methods of optimization are put forwards. The second optimization revolves around the concept of continuation closure. It uses the normal stack frame of standard implementation, but alters its continuation closure to achieve quick procedure exit. The third optimization builds upon the concept of para‐stack frame and common continuation closure for achieving fast procedure exit. Various other refinements are also considered.

By making the moving direction of each disc explicit in the representation, a bit-string so constructed can be used to drive the Tower of Hanoi algorithm. The behaviour of disc moves is further analysed based on the bit-string representation. It has been shown that the bit-string for moving n discs can be used to generate successively the Gray codes of n bits.

The construction of both an optimal read-forward polyphase sort and a near optimal read-backward version is described. The former minimizes the merge volume, for a given distribution of strings, without the use of auxiliary data structures, and incorporates a new technique for computing the positions of dummy strings. In the case of the read-backward version, an approach is developed which achieves a merge volume nearest to the minimum, inasmuch as the theoretical optimal read-backward polyphase sort cannot be realized. A dispersion algorithm is also described which optimizes the distribution of strings so that minimum merge volume is assured.