Generation of Rosary Permutations Expressed in Hamiltonian Circuits Systematic generation of a specific class of permutations fundamental to scheduling problems is described. In a nonoriented complete graph with n vertices, Hamitonian circuits equivalent to .5(n - 1)! specific permutations of n elements, termed rosary permutations, can be defined. Each of them corresponds to two circular permutations which mirror-image each other, and is generated successively by a number system covering 3*4*...*(n-1) sets of edges. Every set of edges {E[k]}, 1 <= E[k] <= k, 3 <= k <= (n-1) is determined recursively by constructing a Hamiltonian circuit with k vertices from a Hamiltonian circuit with k-1 vertices, starting with the Hamiltonian circuit of 3 vertices. The basic operation consists of transposition of a pair of adjacent vertices where the position of the pair in the permutation is determined by {E[k]}. Two algorithms treating the same example for five vertices are presented. It is very easy to derive all possible n! permutations from the .5(n - 1 )! rosary permutations be cycling the permutations and by taking them in the reverse order-procedures which can be performed fairly efficiently by computer. CACM June, 1971 Harada, K. permutation, graph theory, scheduling, combinatorial algebra 5.32 5.39 CA710601 JB February 3, 1978 1:55 PM 2044 4 2189 2087 4 2189 2189 4 2189 2189 4 2189 2189 4 2189 2189 4 2189 2417 4 2189 2505 4 2189 2874 4 2189 2908 4 2189 3188 4 2189 1594 5 2189 2087 5 2189 2189 5 2189 2189 5 2189 2189 5 2189 2292 5 2189 2505 5 2189 521 5 2189 3191 5 2189 2189 6 2189 2189 6 2189 2292 6 2189 521 6 2189