PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 89(103) (2011), 37–47 DOI: 10.2298/PIM1103037K

A LOOPLESS IMPLEMENTATION OF A GRAY CODE FOR SIGNED PERMUTATIONS

James Korsh, Paul LaFollette, and Seymour Lipschutz

Communicated by Slobodan Simić

Abstract. Conway, Sloane and Wilks [1989] proved the existence of a Gray code for the reflection group B_{n}. The elements of this group are the signed permutations of the set 1, 2, …, n. Here we give a loopless algorithm which generates a specific Gray code for B_{n}.

1. Introduction

The original idea of a Gray code was to list all n-bit strings, sequences of 0’s and 1’s of length n, called codewords, so that successive codewords differ in only one bit. Q_{n} is used to denote all codewords of length n. The fact that this can be done for any n follows from the construction of the Binary Reflected Gray Code (BRGC) for Q_{n} (see [5]) which we describe below.

The above idea of a Gray code has been generalized as follows. A Gray code for any combinatorial family of objects is a listing of the objects such that successive objects differ in some prescribed, usually “small", way. The definition of “small" depends on the particular family, its context, and its applications. Gray codes are useful in studying the properties of the objects being generated because the less successively generated objects differ from each other, the faster the properties being studied can be updated in passing from one object to the next. Carla Savage [10] has an excellent survey of Gray codes with 154 references.

Consider, for example, S_{n}, the set of all permutations of the integers 1 to n. A Gray code for S_{n} may be defined to be a list L of the permutations in S_{n} such that successive permutations differ by a transposition, the interchange of two integers. One such famous Gray code for S_{n} was given by Johnson [7] and Trotter [12], apparently independently. In fact, their Gray code uses only adjacent interchanges. We discuss this Gray code in detail later.

2010 Mathematics Subject Classification: Primary 68R05; Secondary 05A05.

Key words and phrases: algorithms; combinatorial; loopless; gray code; reflection groups; signed permutations.

Now consider any finite group G with a set of generators. A Gray code for G is a list L of the elements of G such that each element is obtained from the previous one by applying one of the generators. This is equivalent to a Hamiltonian path in the Caley graph of the group.

Conway, Sloane and Wilks (CSW) [2] proved the existence of a Gray code for all the finite reflection groups; the term reflection comes from the fact that each generator of the group has order two. This includes the infinite family of reflection groups B_{n} (n ⩾ 2) (which are defined below). The elements of these groups are in fact the signed permutations of the set {1, 2, …, n}. Signed permutations are used, for example, in bioinformatics [4, 11, 14]. Rankin [9] showed that the alternating group A(6) with generators (2,4,6,5,3) and (1,6,3)(2,4,5) does not have a Gray code.

We note that an algorithm which generates the elements of a combinatorial family is said to be loopless if it takes no more than a constant amount of time between the elements. Gidean Ehrlich [3] first formulated this notion of a loopless algorithm. This paper gives a loopless algorithm which generates a specific Gray code for B_{n}. The algorithm uses a loopless algorithm by Bitner, Ehrlich and Reingold (BER) [1] for the BRGC for Q_{n}, and our loopless version of the Johnson–Trotter listing for S_{n}.

Our paper is organized as follows. Section 2 discusses the Binary Reflected Gray Code for Q_{n}, and the loopless algorithm generating it by BER [1]. Section 3 discusses the Johnson–Trotter Gray code listing for S_{n} and our loopless algorithm for generating it. Section 4 discusses the reflection group B_{n}, Section 5 discusses our algorithm for its generation, and Section 6 gives two loopless versions of the algorithm. The second version uses integers no larger than n.

2. Binary reflected gray code

Since a Gray code for Q_{n} is a list of all codewords of Q_{n} such that successive codewords differ by only one bit, the Gray code is completely determined by its transition sequence, the list of the bit positions which change as we go from one codeword to the next in the sequence.

There are many Gray codes for Q_{n}. We are only interested in the Binary Reflected Gray Code (BRGC) for Q_{n}. There is a simple recursive construction of this Gray code. Specifically, Table 1 shows how the BRGC for Q_{4} can be obtained from the BRGC for Q_{3}. That is, first we list the Gray code for Q_{3} which appears as the upper left 3 × 8 matrix (where the codewords are the columns). Then next to it we list the Gray code for Q_{3} but in reverse order. This yields a 3 × 16 matrix. Finally, we add a fourth row consisting of eight 0’s followed by eight 1’s. This gives the BRGC for Q_{4}.

We show that this is in fact a Gray code for Q_{4}. Observe that only one bit changes within the first eight columns since the bottom bit is always 0, and only one bit changes within the last eight columns since the bottom bit is always 1. Furthermore, the two middle columns (and also the first and last columns) are identical except for the added last bits, and so again only one bit changes. The BRGC for Q_{n} is the one obtained recursively in this way beginning with the matrix [0, 1] for Q_{1}.

Frank Gray, for whom Gray codes are named, first specified this recursive construction in [6]. Discussing the BRGC, Herbert Wilf [14] comments: “This method of copying a list and its reversal … seems to be a good thing to think of when trying to construct some new kind of Gray code."

T_{4}:

Q_{3}  Q_{3} reversed
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
4 3 4 2 4 3 4 1 4 3 4 2 4 3 4

Table 1. Binary reflected gray code for Q_{4}

Observe that the transition sequence T_{4} = [4, 3, 4, …, 3, 4] for the BRGC for Q_{4} also appears in Table 1, where we view the codewords from the bottom (“first" row) to the top (“fourth" row). That is, first the fourth bit changes, then the third bit changes, then the fourth bit changes again, and then the second bit changes, and so on. BER [1] gave a very clever loopless algorithm which generates the transition sequence T_{n} using an array [t_{0}, t_{1}, t_{2}, …, t_{n}]. We essentially use this algorithm (in our loopless algorithm generating a Gray code for B_{n}) to go both forward and backward in the BRGC for Q_{n}.

3. Johnson–Trotter list

The Johnson–Trotter permutation list is also defined recursively. The list for n = 4 is shown in Table 2. Note that the list is partitioned into six “blocks", each with four successive permutations. Each block corresponds to, and is labeled by, a permutation in S_{3} which is in boldface and is on top of the block. We note that the boldface labels form the Johnson–Trotter list for S_{3}.

123 132 312 321 231 213
1234 4132 3124 4321 2314 4213
1243 1432 3142 3421 2341 2413
1423 1342 3412 3241 2431 2143
4123 1324 4312 3214 4231 2134

Table 2. Johnson–Trotter list for S_{4}

Observe that in the first block, the largest item 4 sweeps from right to left, in the second block from left to right, in the third block from right to left, and so on. Also, the relative positions of the remaining items 1, 2, 3 do not change in each block and correspond to the label of the block. Moreover, the recursive changes of the relative positions of 1, 2, and 3 occur only from block to block when the largest item 4 is in an end position so the item 4 does not interfere with any transposition involving the items 1, 2, and 3. Thus the Johnson–Trotter list JT(n) is a Gray code for S_{n}. (In fact, successive permutations in JT(n) differ by only an adjacent transposition.)

Ehrlich [3] gave the first loopless algorithm to generate the Johnson–Trotter list. An alternate loopless algorithm for the JT list appears in [8]. We have to move both forward and backward in the JT list, so our algorithm, although similar to the Ehrlich [3] algorithm, will be more involved. We describe one part of our algorithm as follows.

Suppose we first consider moving forward in the JT list. We use two arrays d and e which we describe below.

(a) Each item (number) in any permutation has a direction, LEFT or RIGHT. Whenever the item reaches an end position in its respective subpermutation it changes its direction. All items begin with the direction (moving) LEFT. (For example, the item 4, in Table 2, changes its direction from LEFT to RIGHT after the fourth permutation 4123 where 4 has reached an end position.) Array d will contain the directions of the items in the permutations.

(b) Our algorithm implicitly uses two lists, a “mobile" list and a “finished" list, and the lists are ordered with the largest element first. Each item is on exactly one of the two lists. The item that moves will be the first element on the mobile list and, when it moves, all larger items on the finished list are inserted at the beginning of the mobile list, retaining their relative order. An item on the mobile list is moved to the finished list when it reaches an end position in its respective subpermutation. The algorithm ends when the mobile list is empty or, equivalently, when all items are on the finished list. Array e keeps track of the items on the mobile lists and on the finished lists. Similarly, we use arrays D and E, analogous to d and e, when moving backward in the JT list.

To explain how these arrays can be updated in constant time consider array e. The item at the front of the mobile list is always in e[n + 1]. If this item is j, then its successor, j1, will be in e[j]. Similarly, j1’s successor will be in e[j1] and so on. As an example, if n is 6 and e[1] e[2] e[3] e[4] e[5] e[6] e[7] are 0 1 1 3 4 5 4, then the list is 1, 3, 4 where 4 is e[7], 3 is e[4], and 1 is e[3]. The finished list contains items not on the mobile list (2, 5, and 6 here).

If the moving item j finishes, it must be removed from the list. It is removed by setting e[j + 1] to e[j]. This works because e[j + 1] must hold the successor of j + 1 in the updated list and this successor is the current successor of j, which is in e[j].

In addition, e[j] is set to j − 1. Since j can move only when j + 1 to n are all finished, as j+1 to n finish, this will have set e[j+1] to j, e[j+2] to j+2, …, and e[n] to n−1. Consequently, when e[n+1] is set to n, the list becomes j +1, j +2, …, n.

If the moving item does not finish, then n should become the item at the front of the list and setting e[n + 1] to n accomplishes this.

E must also be updated. Remember that E controls the reverse generation of S_{n}. When j is finished, this entails simply setting E[n+1] to j. Suppose j is not finished. If E[j + 1] is j, then j is on the mobile list of E so all that is required is again setting E[n + 1] to j. However, if E[j + 1] is not j, then j must have finished (in the reverse generation) and so was taken off E’s list by first setting E[j + 1] to E[j] and then setting E[j] to j − 1. Restoring it requires first setting E[j] to E[j + 1] then setting E[j + 1] to j and again setting E[n + 1] to j.

These changes and determining when j is finished take at most constant time. Updating d and D is straightforward and also takes at most constant time.

4. Reflection group B_{n}

The reflection group B_{n} with generators R_{1}, R_{2}, …, R_{n} may be represented by the permutations of 1, 2, …, n with each integer having a + or − sign attached to it, so each integer can be positive or negative – the signed permutations. (We will let boldface numbers indicate integers with − signs.) Thus B_{n} has order 2^{n}n!. In particular, B_{2} has |B_{2}| = 2^{2}2! = 8 elements which follow:

B_{2} : {12, 12, 21, 21, 12, 12, 21, 21}

The generators R_{1}, R_{2}, …, R_{n−1} of B_{n} correspond to the adjacent transpositions (12), (23), (34), …, (n − 1, n) and hence R_{1}, R_{2}, …, R_{n−1} generate a subgroup H of B_{n} which is isomorphic to S_{n}. The generator R_{n} changes the sign of the last coordinate. Observe that the above list for B_{2} is in fact a Gray code for B_{2}.

Using 0 to denote + and 1 to denote −, an element z in B_{n} may be represented by a pair (p, g) where:

(i) p (for permutation) belongs to S_{n}: p is the list of the numbers in z without

any signs; and

(ii) g (for Gray code) belongs to Q_{n}: g denotes the numbers (not positions) in

z which are negative. For example:

z = 364251 in B_{6} corresponds to (364251, 010011) and
z = 41856327 in B_{8} corresponds to (41856327, 00110001)

Our algorithm will output the elements of B_{n} as pairs (p, g). We will illustrate our algorithm using B_{3} and then B_{4} as examples.

Table 3 pictures B_{3}, where the |B_{3}| = 2^{3}3! = 48 elements of B_{3} are arranged in an array. Note that the columns of the array are labeled by the BRGC for Q_{3} and the rows are labeled by the Johnson–Trotter list for S_{3}.

The first column H under 000, which consists of all permutations where the signs are all +, is the subgroup H of B_{3}, which is isomorphic to S_{3}. Each of the other columns is a coset of H. Since the first column H is a Johnson–Trotter list for S_{3}, we can move up or down any column using the generators R_{1}, R_{2}, …, R_{n−1} . On the other hand, we can move between adjacent columns using only the generator R_{n} which negates the last item in the permutation. The double arrow in Table 3 indicates an edge between the adjacent cosets (columns). Observe there are exactly two edges between any two adjacent columns.

Our algorithm will generate the following Hamiltonian path (Gray code) for B_{3}:

000 001 011 010 110 111 101 100
123 123 ↔ 123 123 ↔ 123 123 ↔ 123  123 ↔ 123
132 132 132 ↔ 132 132 132 132 ↔ 132 132
312 312 312 ↔ 312 312 312 312 ↔ 312 312
321 321 321 321 321 ↔ 321 321  321 321
231 231 231 231 231 ↔ 231 231  231 231
213 213 ↔ 213 213 ↔ 213 213 ↔ 213  213 ↔ 213

Table 3. Reflection group B_{3}

123 → 123, 132 → 132, 123 → 123, 132, 312, 321 → 321, 312, 132, 123 → 123, 132 → 132, 123→123 and down the column to 213 ↦ 213, 231, 321, 312 ↦ 312, 321, 231, 213 ↦ 213, 231 ↦ 231, 213 ↦ 213, 231, 321, 312 ↦312, 321, 231, 213 ↦213 and up the column to 132. That is, the path moves from the first column to the last and then back again, and:

(i) Each of the seven → denotes a move from a column to the next column. (ii) Each of the seven ↦ denotes a move from a column to the preceding column. (iii) Each comma “," denotes a move up or a move down within a column. It would be very instructive if the reader followed the path through Table 3. Table 4 pictures B_{4} where the |B_{4}| = 2^{4}4! = 384 elements of B_{4} are again

arranged in an array. The columns are labeled by the BRGC for Q_{4} and the rows are labeled by the Johnson–Trotter list for S_{4}. Here a star ∗ is used instead of ↔ to denote an edge between columns. Observe that here there are six edges between adjacent columns. We will also use the underlined star \underline{∗} to denote the first edge between the columns.

5. Algorithm generating a gray code for B_{n}

This section presents our algorithm generating a Gray code for B_{n} which is similar to the one for B_{3}. First of all we assume the elements of B_{n} are arranged in an array where the columns of the array are labeled by the BRGC for Q_{n} and the rows are labeled by the Johnson–Trotter list for S_{n}. (This was done in Table 3 for B_{3} and in Table 4 for B_{4}).

The first column H under 00… 0 is the subgroup of B_{n} which is isomorphic to S_{n}, and each of the other columns is a coset of H. There will always be an edge in our path for B_{n} in the first row and in the last row between each odd column and the next even column, that is, between columns 1 and 2, between columns 3 and 4, and so on until between (the last two) columns 2^{n} − 1 and 2^{n}. These edges will be called special edges.

Our path will have two parts, A and B, where A moves forward through the array and down the last column and B moves backward through the array and up the first column. Specifically:

(A) Part A begins at the element x = 123 …n (in the first row, first column). Then either:

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
1234 1234 \underline{∗} 1234 1234 \underline{∗} 1234 1234 \underline{∗} 1234 1234 \underline{∗} 1234 1234 \underline{∗} 1234 1234 \underline{∗} 1234 1234 \underline{∗} 1234 1234 \underline{∗} 1234
1243 1243 1243 \underline{∗} 1243 1243 1243 1243 \underline{∗} 1243 1243 1243 1243 \underline{∗} 1243 1243 1243 1243 \underline{∗} 1243 1243
1423 1423 1423 ∗ 1423 1423 1423 1423 ∗ 1423 1423 1423 1423 ∗ 1423 1423 1423 1423 ∗ 1423 1423
4123 4123 4123 ∗ 4123 4123 4123 4123 ∗ 4123 4123 4123 4123 ∗ 4123 4123 4123 4123 ∗ 4123 4123
4132 4132 4132 4132 4132 \underline{∗} 4132 4132 4132 4132 4132 4132 4132 4132 \underline{∗} 4132 4132 4132 4132
1432 1432 1432 1432 1432 ∗ 1432 1432 1432 1432 1432 1432 1432 1432 ∗ 1432 1432 1432 1432
1342 1342 1342 1342 1342 ∗ 1342 1342 1342 1342 1342 1342 1342 1342 ∗ 1342 1342 1342 1342
1324 1324 ∗ 1324 1324 ∗ 1324 1324 ∗ 1324 1324 ∗ 1324 1324 ∗ 1324 1324 ∗ 1324 1324 ∗ 1324 1324 ∗ 1324
3124 3124 ∗ 3124 3124 ∗ 3124 3124 ∗ 3124 3124 ∗ 3124 3124 ∗ 3124 3124 ∗ 3124 3124 ∗ 3124 3124 ∗ 3124
3142 3142 3142 3142 3142 ∗ 3142 3142 3142 3142 3142 3142 3142 3142 ∗ 3142 3142 3142 3142
3412 3412 3412 3412 3412 ∗ 3412 3412 3412 3412 3412 3412 3412 3412 ∗ 3412 3412 3412 3412
4312 4312 4312 4312 4312 ∗ 4312 4312 4312 4312 4312 4312 4312 4312 ∗ 4312 4312 4312 4312
4321 4321 4321 4321 4321 4321 4321 4321 4321 \underline{∗} 4321 4321 4321 4321 4321 4321 4321 4321
3421 3421 3421 3421 3421 3421 3421 3421 3421 ∗ 3421 3421 3421 3421 3421 3421 3421 3421
3241 3241 3241 3241 3241 3241 3241 3241 3241 ∗ 3241 3241 3241 3241 3241 3241 3241 3241
3214 3214 ∗ 3214 3214 ∗ 3214 3214 ∗ 3214 3214 ∗ 3214 3214 ∗ 3214 3214 ∗ 3214 3214 ∗ 3214 3214 ∗ 3214
2314 2314 ∗ 2314 2314 ∗ 2314 2314 ∗ 2314 2314 ∗ 2314 2314 ∗ 2314 2314 ∗ 2314 2314 ∗ 2314 2314 ∗ 2314
2341 2341 2341 2341 2341 2341 2341 2341 2341 ∗ 2341 2341 2341 2341 2341 2341 2341 2341
2431 2431 2431 2431 2431 2431 2431 2431 2431 ∗ 2431 2431 2431 2431 2431 2431 2431 2431
4231 4231 4231 4231 4231 4231 4231 4231 4231 ∗ 4231 4231 4231 4231 4231 4231 4231 4231
4213 4213 4213 ∗ 4213 4213 4213 4213 ∗ 4213 4213 4213 4213 ∗ 4213 4213 4213 4213 ∗ 4213 4213
2413 2413 2413 ∗ 2413 2413 2413 2413 ∗ 2413 2413 2413 2413 ∗ 2413 2413 2413 2413 ∗ 2413 2413
2143 2143 2143 ∗ 2143 2143 2143 2143 ∗ 2143 2143 2143 2143 ∗ 2143 2143 2143 2143 ∗ 2143 2143
2134 2134 ∗ 2134 2134 ∗ 2134 2134 ∗ 2134 2134 ∗ 2134 2134 ∗ 2134 2134 ∗ 2134 2134 ∗ 2134 2134 ∗ 2134

Table 4. Reflection group B_{4}

(i) it will move from one column to the next column using the topmost edge between successive columns. This edge is alternately the top special edge and another topmost edge, starting and ending with the top special edge or

(ii) it will move up or down within a column. After arriving at the last column using the top special edge it will move all the way down the last column to the last entry y = 213 …n in the column.

(b) Part B begins at the element y (in the last row, last column). Then either:

(i) it will move from one column to the preceding column using alternately the bottom special edge and the edge just below the topmost edge between successive columns (which is not a top special edge), starting and ending with the bottom special edge or

(ii) it will move up or down within a column. After arriving at the first column using the bottom special edge it will move all the way up the first column to its second entry, 123 …(n − 2)n(n − 1).

It would be instructive if the reader used our algorithm to follow the Gray code for B_{4} in Table 4. We note that we move from Column 4 to Column 5 in Row 5, and hence on the way back we move from Column 5 to Column 4 in Row 6. Similarly, we move from Column 8 to Column 9 in Row 13, and hence on the way back we move from Column 9 to Column 8 in Row 14.

The path this algorithm traces is Hamiltonian because each topmost edge that is not the top special edge has a second edge immediately below it in the next row. In Section 6 we will see that this second edge always exists.

Note that this Gray code is circular since the last element differs from the first by an adjacent interchange, so the Hamiltonian path we generate can be extended to a Hamiltonian cycle by adding one more edge.

We emphasize that there are many Gray codes for B_{n}. We use the first edge when moving forward; but other edges could also have been used to yield a Gray code for B_{n}. It is important to note that we cannot simply generate entire columns, one after another, because the generator R_{n} must be used to go between columns.

6. Loopless algorithm for our gray code for B_{n}

Implementing our algorithm looplessly, we need to do the following three things:

(1) Looplessly move from one column to an adjacent column or, equivalently, looplessly move between elements of the BRGC for Q_{n}. This we do using a modification of the algorithm by BER [1].

(2) Looplessly move up and down a column or, equivalently, looplessly move between elements of the symmetric group S_{n}. This we do using a loopless version of the JT list. This version uses the arrays d, e, D and E described above. When moving down, our algorithm uses d and e and looplessly updates D and E; and when moving up it uses D and E and looplessly updates d and e.

(3) Keep track of each row where we move from one column to the next column so on the way back we know the row we must use to go backward. This can be done in two different ways:

(a) We can use an array to keep track of the row position when we move to the next column. Unfortunately the row position may be a very large number, that is, of order n!.

(b) We can keep in memory a two-dimensional n × n array r whose rows are the permutations corresponding to those edges where we move forward from one column to the next.

For example, for B_{4}:

r = [ \begin{matrix}4 & 3 & 2 & 1 \\ 4 & 1 & 3 & 2 \\ 1 & 2 & 4 & 3 \\ 1 & 2 & 3 & 4 \end{matrix}] .

The numbers in the last column are all different since we move from column to column depending on the last number in the permutation. Row s of array r is always the first permutation in the JT list, where s occurs at the right end of the permutation. Also, s is the position of the bit that changes in the codeword as we move to the next column.

When s < n, row s is where our algorithm moves forward to the next column using a topmost edge that is not the top special edge. Since s will have just occurred at the right end, s must remain at the right end in the next row with its sign unchanged and the element to its right must differ from it only in the sign of s. The next element in the path traced by our algorithm is in the same row as row s but the next column and differs from row s only in the sign of s. Hence there is always an edge in the row just below row s.

In general, row s has the form

[evens > (s + 2)], (s + 2), 1, 2, …, (s − 1), (s + 1), [odds > (s + 2)], s

where the evens decrease from left to right and the odds increase from left to right. For example, for n = 16 and s = 7, we have the row

16, 14, 12, 10, 9, 1, 2, 3, 4, 5, 6, 8, 11, 13, 15, 7

This second version uses only integers that are no larger than n.

We also point out that this version must looplessly determine when, as it moves up a column on the way back, it has encountered the permutation corresponding to the (first) edge where it earlier moved forward to the current column. When that permutation is encountered, we backtrack to the edge below it and then move left to the preceding column. Since the last permutation in each column is always 2134 …n, it is not necessary to check for that permutation until p[n] is s in the current permutation. After that has occurred, we compare exactly one item in the current permutation with the corresponding item in row s of the array r. There are only two cases that can occur for this comparison, when the first item of row r, r[s][1] is n, and when it is not n. These are illustrated below for n = 7. When s is 5, row s is 7 1 2 3 4 6 5 so r[s][1] is 7 and when s is 4, row s is 6 1 2 3 5 7 4 so r[s][1] is not 7:

s = 5 s = 4

7 1 2 3 4 6 5 1 7 2 3 4 6 5 1 2 7 3 4 6 5 1 2 3 7 4 6 5 1 2 3 4 7 6 5 1 2 3 4 6 7 5  6 1 2 3 5 7 4 6 1 2 3 7 5 4 6 1 2 7 3 5 4 6 1 7 2 3 5 4 6 7 1 2 3 5 4 7 6 1 2 3 5 4

These are the permutations that are encountered when moving up in a column looking for row s in the two cases. In the first case, n = 7 is moving left and in the second case, n = 7 is moving right. We can looplessly determine when row s has been reached by checking that the corresponding item in the current permutation matches the boldface item in row s. When all these required matches have occurred, we are at the permutation we must backtrack from.

Our two loopless algorithms for n > 2 written in C^{++} , are available at: http://www.cis.temple.edu/~korsh/reflectionswithcounts.c++ and http://www.cis.temple.edu/~korsh/reflectionswithnocounts.c++ Both programs represent the elements using an array g and an array p as

described in Section 4. Array p contains positive integers from 1 to n.

Two loopless programs which represent the elements more directly as signed permutations using an array p of positive and negative integers from 1 to n are available at:

http://www.cis.temple.edu/~korsh/signedpermutationswithcounts.c++ and http://www.cis.temple.edu/~korsh/signedpermutationswithnocounts.c++

Acknowledgement. The authors would like to thank a referee for suggestions which significantly improved the paper.

References

1. J. R. Bitner, G. Ehrlich, and E. M. Reingold, Efficient generation of the binary reflected Gray code and its applications, Comm. Assoc. Comput. Mach. 19 (1976), 517–521.

2. J. H. Conway, N. J. A. Sloane and A. R. Wilks, Gray codes for reflection groups, Graphs Combin. 5 (1989) 315–325.

3. G. Ehrlich, Loopless algorithms for generating permutations, combinations, and other combinatorial configurations J. Assoc. Comput. Mach. 20 (1973), 500–513.

4. M. Figeac and J.-S. Varre, Sorting by Reversals with Common Intervals, in: Algorithms in Bioinformatics: 4th International Workshop, WABI 2004, Bergen, Norway, September 17– 21, 2004, Proceedings (Lect. Notes Comput. Sci. and Lect. Notes Bioinformatics), 26–37.

5. E. N. Gilbert, Gray codes and paths on the n-cube, Bell Syst. Tech. J. 37 (1958), 815–826.

6. F. Gray, Pulse code communication, March 17, 1953 (filed Nov. 1947). U.S. Patent 2,632,058.

7. S. M. Johnson, Generation of permutations by adjacent transposition, Math. Comput. 17 (1963), 282–285.

8. J. Korsh and S. Lipschutz, Generating multiset permutations in constant time, J. Algorithms 25 (1997), 321–335.

9. R. A. Rankin, A campanological problem in group theory, Proc. Camb. Philos. Soc. 44 (1948), 17–25.

10. C. Savage, A survey of combinatorial Gray codes, SIAM Rev. 39(4) (1997), 605–629.

11. K. M. Swenson, V. Rajan, Yu Lin, and B. M. Moret, Sorting Signed Permutations by Inversions in O(n log n) Time, RECOMB 2’09, Proc. 13th Annual Internat. Conf. on Research in Computational Molecular Biology, 386–399.

12. H. F. Trotter, Algorithm 115, Permutations, Comm. Assoc. Comput. Mach. 5 (1962), 434– 435.

13. H. Wilf, Combinatorial Algorithms – an Update, SIAM, Philadelphia, 1989.

14. S. Yancopoulos, O. Attie, and R. Friedberg, Efficient sorting of genomic permutations by translocation, inversion and block interchange, Bioinformatics 21(16) (2005), 3340–3346.

Department of CIS (Korsh and LaFollette) (Received 06 01 2010) Department of Mathematics (Lipschutz) (Revised 19 01 2011 and 08 02 2011) Temple University Philadelphia, PA 19122 U.S.A.

          korsh@temple.edu
paul.lafollette@temple.edu
        seymour@temple.edu