We apply a genetic algorithm whose genotypes represent simple grammars to search for families of compare-exchange networks that are merging networks. The grammars are restricted to be of a simple form based on prior knowledge about the search domain. Finding merging networks in this fashion leads to the discovery of networks that also sort if the data is cycled through them a small number of times. Random network and grammar generation results show that the problem is difficult and suggest some conjectures about how the genetic algorithm is operating for this problem. The genetic algorithm finds the best-known network of the kind for which we search, and further finds a novel, slightly suboptimal network that turns out to be an interesting combination of ideas from known, theoretically derived networks.

Lel G = (V, E) be a nonplanar graph.The method of using depth-first techniques to extract a Kuratowski .,;ubgraph in time O( I V[ ) is shown.

We consider families $\{ {\bf C}(n,k):O \leqq k \leqq n\} $ where each ${\bf C}(n,k)$ is a set of combinatorial objects, $C(n,k) = |{\bf C}(n,k)|$ satisfies a recursion $C(n,k)= a_{n,k}C(n - 1,k - 1) + b_{n,k} C(n - 1,k)$, and each object in ${\bf C}(n,k)$ is represented by an n-vector. We study “loop-free” or “uniformly bounded transition” algorithms, i.e., algorithms which yield linear orders on the sets ${\bf C}(n,k)$ so that the vectors representing consecutive objects are “close to each other” (combinatorial Gray codes).Key words. listing algorithms, uniformly bounded operations, uniformly bounded transition algorithms, loop-free algorithms, binary reflected Gray codes, combinatorial Gray codes, binomial grids

This paper discusses determination of the ranks, in lexicographic lists, of the symmetries and proper symmetries of the n-cube and of its colorations by r colors, up to these symmetries.

Given an algorithm for producing a list of objects, a “ranking” algorithm or “sequential numbering scheme“ is a rule $\rho $ which, given an object x, computes its position $m = \rho (x)$ in the list. The associated algorithm for computing $\rho ^{ - 1} $, produces the object x given its position m. In this paper, we consider the objects to be various classes of partitions of a set S. We consider ranking algorithms for lists of all ordered partitions, ordered partitions corresponding to a given multinomial index, all unordered partitions, unordered partitions with a bounded number of blocks, unordered partitions with a fixed number of blocks, unordered partitions with blocks of equal size, unordered partitions corresponding to a fixed ordered partition, and unordered partitions of specified block type. These ranking algorithms are frequently useful for organizing computations associated with the above lists. The computation of $\rho ^{ - 1} $ at a randomly selected m provides a method for the random selection of elements from any of these lists.

Let G be a finite group acting on a finite set S and hence on $\Pi (S)$, the lattice of partitions of S. Computational methods are developed for enumerating the invariants of this action.

A basic algorithm for solving many discrete problems is the so-called “backtracking” algorithm. The basic problem is that of generating the elements of a subset $S_0 $ of a finite set in an efficient manner. If a group G acts on $S_0 $, then one might wish to obtain only nonisomorphic elements of $S_0 $. In this paper the basic backtracking algorithm is described in terms of chains of partitions on the set S. The corresponding isomorph rejection problem is described in terms of G-invariant chains of partitions on S. Examples and flow charts are given.

Let G be a group acting on a finite set S. Let L be a G-stable subset of S and denote by $\Delta $ a transversal for the orbit partition of G acting on L. The problem of devising efficient generating algorithms for $\Delta $ is called the “isomorph rejection” problem. Given a field F of characteristic zero, let $F^S $ denote all functions from S to F. Note that $F^S $ is an algebra under the operations of pointwise addition and multiplication. The problem of generating $\Delta $ or $I_\Delta $ (the Indicator or characteristic function of $\Delta $) may be regarded as a special case of the problem of generating and representing functions $\varphi $ in $F^S $ (in case $\varphi = I_\Delta $). In this context, instead of attempting to generate $I_\Delta $ directly one may instead choose a pair of linear operators $(T_0 ,T_1 )$ and attempt to construct functions $v_1 , \cdots ,v_p $ in $F^S $ such that $T_0 (v_1 + \cdots + v_p ) = T_1 (I_\Delta )$. The construction of $(v_1 , \cdots ,v_p )$ may be regarded as a “weak solution” to the isomorph rejection problem (which becomes an actual solution if $T_0 = T_1 = {\text{identity}}$). In this paper properties of such constructions are considered in the interesting case where $S = R^D $ is itself a finite function set and the operators $T_0 $ and $T_1 $ are constructed from representations of the group G as operators on $F^S $. The extraction of information from such weak solutions is carried out by means of linear functionals on $F^S $. In this setting certain functionals yield information about the cardinality of $\Delta $ in the form of various well-known identities due to deBruijn and Pólya. Some examples of weak solutions to isomorph rejection problems are given.