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