FOR THE GENERATION OF SYMMETRY-INVARIANT PERMUTATIONS

FOR THE GENERATION OF SYMMETRY-INVARIANT PERMUTATIONS

OSCAR MORENO, JOHN RAMÍREZ, DOROTHY BOLLMAN, AND EDUSMILDO OROZCO

Received 5 March 2002

A new backtracking algorithm is developed for generating classes of per- mutations, that are invariant under the groupG4of rigid motions of the square generated by reflections about the horizontal and vertical axes.

Special cases give a new algorithm for generating solutions of the classi- caln-queens problem, as well as a new algorithm for generating Costas sequences, which are used in encoding radar and sonar signals. Parallel implementations of this latter algorithm have yielded new Costas se- quences for lengthn, 19≤n≤24.

1. Introduction

Backtracking is a general procedure for solving a problem by systemat- ically generating all possible solutions. Such a process can be described by a search tree in which each node corresponds to a partial solution. Go- ing down the tree corresponds to progress toward obtaining a complete solution. Going up the tree, that is,backtracking, corresponds to returning to a partial solution from which it might be hopeful to proceed forward again.

In this paper, we give a new backtracking algorithm for the generation of certain permutation matrices, that is, square matrices of 0’s(or blanks) and 1’s(or dots), in which each column or row contains exactly one 1.

An example of such a matrix is given inFigure 2.1.

It is convenient to representn×npermutation matrices by sequences xi, i=1,2, . . . , n, where each xi is the row number in which column i has its dot. Such a sequence is a permutation of the elements ofNn= {1,2, . . . , n}, or more precisely, the sequences of images of a bijection

Copyright^c2002 Hindawi Publishing Corporation Journal of Applied Mathematics 2:6(2002)277–287

2000 Mathematics Subject Classification: 94A55, 05C30, 68W10 URL:http://dx.doi.org/10.1155/S1110757X02203022

π :Nn→Nn. We denote the set of bijections π :Nn→Nn byΠn. We will denote permutations interchangeably by either bijections π or the sequence of imagesπ(Nn) =π(1)π(2)···π(n).

We develop an algorithm for generating classes of permutations of Nn, that are invariant under the groupG4of rigid motions of the square generated by reflections about the horizontal and vertical axes. This al- gorithm uses backtracking, but differs from usual backtracking algo- rithms in two aspects.

First, our algorithm adds terms to both(not just one) sides of a se- quence. An intuitive comparison between ordinary backtracking and ours is as follows. An application of ordinary backtracking would not distinguish between unwanted patterns at the beginning and at the end of a sequence. That is, a sequence could be rejected because of an un- wanted pattern at the beginning, but ordinary backtracking would gen- erate another sequence with the same pattern, say closer to the end. The idea of the algorithm presented here is that adding characters to both sides of the sequence would eliminate this redundancy, thus making the algorithm much faster.

The second source of speedup exploits invariance under the groupG4. Using this fact, it is necessary to use backtracking to generate only as few as one-fourth of the permutations of a given class and a given size.

The rest of this paper is organized as follows: inSection 2, we define the above-mentioned symmetries and develop the background neces- sary to present the algorithm. InSection 3, we give the algorithm and prove its correctness. InSection 4, we briefly discuss results of applying the algorithm to the generation of Costas arrays.

2. Permutation symmetries

The group of symmetriesG4greatly reduces the size of the search space for certain sets of permutations.G4 is a subgroup of the group of rigid motions of the square onto itself, namely, the group generated by reflec- tions about vertical and horizontal axes, that is, reversing the columns or the rows of the permutation matrix, respectively. Thus the result of reflecting the array ofFigure 2.1about the vertical axis gives the array in Figure 2.2, and the result of reflecting it about the horizontal axis gives the array inFigure 2.3.

In the sequence representationσ=π(Nn)of a permutation matrix, the reflection about the vertical axis is represented by the sequence obtained fromσby reversing its terms, and the reflection about the horizontal axis is represented by the sequence obtained fromσ by replacing each term π(i)by its complementn+1−π(i). We denote these operations on per- mutation sequences byf1(σ) =σ˜ andf2(σ) =−σ, respectively. Clearly,

•

•

•

•

• Figure2.1

•

•

•

•

• Figure2.2

•

•

•

•

• Figure2.3

G4={e, f1, f2, f3=f1◦f2}, whereedenotes the identity operation, con- stitutes a group under composition◦.

For any propertyPof permutations, that is,

P:

n∈N

Πn−→ {true, false}, (2.1)

whereN is the set of positive integers, letUP be the set of permutation sequences of one or more elements ofNthat satisfyP, and letUⁿ_P ={σ∈ UP |σis of lengthn}. We say thatUP issymmetry-invariant(SI)permu- tation if for everyσ=π(Nn)∈UP, we havefi(σ)∈UP,i=1,2,3.

Examples

(1)Costas sequences.The condition under which a permutationπ∈Πis a Costas sequence can be stated in terms of thedifference triangle. The first row of the difference triangle is formed by taking differences of adjacent terms. The second row is formed by taking differencesπ(i+2)−π(i),

i=1,2, . . . , n−2 of distance 2 apart. In general, thejth row of the differ- ence triangle is given byπ(i+j)−π(i),i=1,2, . . . , n−j. TheCostas con- ditionstates that no row of the difference triangle should have repeated terms. The set of Costas sequences is symmetry-invariant.

(2)n-queens sequences.These sequences arise from then-queens prob- lem, which is the problem of placingnqueens on ann×nchessboard, so that no two queens are in the same row, column, or diagonal. A permu- tationσ=π(Nn)is ann-queens sequenceif and only if|π(i+d)−π(i)| =d for all i=1,2, . . . , n−dand alld=1,2, . . . , n−1. The set of n-queens se- quences is symmetry-invariant.

We call a permutation σ=π(Nn) a fixed pointif f(σ) =σ for some f∈G4.

Lemma2.1. Ifσ=π(Nn)is fixed for somef∈G4, thenf=f3.

Proof. Letσ=π(Nn). If−σ=σ, thenn+1−π(i) =π(i), that is, 2π(i) = n+1 for all i, which contradicts thatσ is a permutation. If ˜σ=σ, then π(i) =π(n−i+1)for alli, which also contradicts thatσis a permutation.

Hence neitherf=f1norf=f2, and sof=f3.

It is important to note that not all sets of permutations have fixed points. Consider, for example, a propertyP for whichP(π)is true if and only if no two differences of distinct adjacent terms are equal. Such aP is called anadjacent differenceproperty. An important special case is the

Costas condition.

Lemma2.2. IfPis an adjacent difference property, then the setUPhas no fixed points.

Proof. Suppose to the contrary that there exists a fixed pointσ=π(Nn) inP. Thenσ=−σ, and so˜ π(m) +π(n−m+1) =n+1 for allm=1,2, . . . , n.

In particular, π(1) +π(n) =n+1 and π(2) +π(n−1) =n+1. Hence, π(2)−π(1) =π(n)−π(n−1), which contradicts that P is an adjacent difference property.

In what follows,r denotes an arbitrary but fixed number inNn, and qrorqdenotes the complement ofr, that is,q=n+1−r. Now let

F_n^r(P) = σ=π

Nn

∈Uⁿ_P|π(i) =r, π(j) =q, i≤j∧ −σ˜=σ , A^r_n(P) =

π Nn

∈Uⁿ_P|π(i) =r, π(j) =q, 1< i < j

∧

n+1> i+j∨

n+1=i+j∧π(m) +π(n−m+1)> n+1 , B_n^r(P) =

π Nn

∈Uⁿ_P|π(1) =r, π(n) =qand π(m) +π(n−m+1)< n+1

, (2.2)

where each occurrence ofmdenotes the least index, for whichπ(m) + π(n−m+1)=n+1. Finally, let

S^r_n(P) =A^r_n(P)∪B_n^r(P). (2.3) Note that all elements ofS^r_n(P)have the property thatr precedesq, and that the number of positions to the right ofqis not less than the number of positions to the left ofr.

Let

S˜^r_n(P) =

σ˜ |σ∈S^r_n(P) ,

−S^r_n(P) =

−σ|σ∈S^r_n(P) ,

−S˜^r_n(P) =

−σ˜ |σ∈S^r_n(P) .

(2.4)

We will denoteS^r_n(P)byS^r_nwhen there is no ambiguity. Similarly, for A^r_n(P),B^r_n(P),−S^r_n(P), ˜S^r_n(P), and−S˜^r_n(P).

Lemma2.3. The setsS^r_n,S˜^r_n,−S^r_n, and−S˜^r_nare pairwise disjoint for any fixedP. Proof. First note that none of the above sets contains a fixed point. Thus, we can assume that there exists a least indexmfor whichπ(m) +π(n+ m−1)=n+1. Also note that the r in anyσ∈S^r_n∪ −S˜^r_n precedes theq, whereas therin anyσ∈ −S^r_n∪S˜^r_nfollowsq. Hence

S^r_n∩ −S^r_n=φ, S^r_n∩S˜^r_n=φ,

−S˜^r_n∩ −S^r_n=φ,

−S˜^r_n∩S˜^r_n=φ.

(2.5)

Now suppose thatσ=π(n)∈S^r_n∩ −S˜^r_n. Sinceσ∈S^r_n, the number of positions to the right of qis n−j≥0. Ifn−j=0, then σ∈B^r_n, and so π(m) +π(n−m+1)< n+1;

n+1−π(n−m+1) +n+1−π(m)> n+1, (2.6) which contradicts thatσ∈ −S˜^r_n.

Thusn > j, and soσ∈A^r_n. In this case,n−j≥i−1>0. But sinceσ∈

−S˜^r_n, we also have that the number of positions in−σ˜ to the right ofqis greater than or equal to the number of positions to the left ofr. That is, n−(n+1−i) =i−1≥n+1−j−1=n−j. Thus,n−j=i−1 orn+1=i+j, and so−σ˜ ∈A^r_n. Hencen+1−π(n−m+1) +n+1−π(m)> n+1, and so

π(n−m+1) +π(m)< n+1, which contradicts thatσ∈A^r_n. Thus,

S^r_n∩ −S˜^r_n=φ. (2.7) Finally, suppose thatσ∈ −S^r_n∩S˜^r_n=φ. Then ˜σ∈ −S˜^r_n and ˜σ∈S^r_n, that is, ˜σ∈ −S˜^r_n∩S^r_n, a contradiction. Hence,

−S^r_n∩S˜^r_n=φ. (2.8) Lemma2.4. The setsS^r_n,S˜^r_n,−S^r_n, and−S˜^r_n are equivalent, that is, have the same number of elements.

Proof. The functionf:S^r_n→S˜^r_ndefined byf(σ) =σ˜ is a bijection. Hence, S^r_nand ˜S^r_n are equivalent, writtenS^r_n≡S˜^r_n. Similarly,S^r_n≡ −S^r_n andS^r_n≡

−S˜^r_n. HenceS^r_n≡S˜^r_n≡ −S^r_n≡ −S˜^r_n.

Theorem2.5. For any symmetry-invariant propertyP,

Uⁿ_P =S^r_n(P)∪S˜^r_n(P)∪ −S^r_n(P)∪ −S˜^r_n(P)∪F_n^r(P)∪ −F_n^r(P). (2.9) Proof. Clearly,

S^r_n∪S˜^r_n∪ −S^r_n∪ −S˜^r_n∪F_n^r∪ −F_n^r⊂Uⁿ_P. (2.10) Now letσ=π(Nn)∈Uⁿ_P. Then eitherπ(i) =r precedesπ(j) =qinσ or not. Suppose it does.

Case1. Suppose thati=1. Ifj < n, thenσ∈S^r_n∪F_n^r. Now supposej=n.

Then eitherσ∈F_n^ror there exists a least indexmfor whichπ(m) +π(n− m+1)=n+1. Supposeσ /∈F_n^r. Ifπ(m) +π(n−m+1)< n+1, thenσ∈S^r_n. Ifπ(m) +π(n−m+1)> n+1, thenn+1−π(m) +n+1−π(n−m+1)<

n+1 and so−σ˜ ∈S^r_n, that is,σ∈ −S˜^r_n.

Case2. Suppose that i >1. Ifn−j > i−1, then σ∈S^r_n. Suppose n−j = i−1. Then either σ∈F_n^r(P), or there exists a leastm such that π(m) + π(n−m+1)=n+1. Supposeσ /∈F_n^r(P). If π(m) +π(n−m+1)> n+1, then σ∈S^r_n. If π(m) +π(n−m+1)< n+1, then n+1−π(m) +n+1− π(n−m+1)> n+1, and soσ∈ −S^r_n. Now, suppose thatn−j < i−1. The number of positions to the left ofr in −σ˜ isn+1−j−1=n−j, and the number of positions to the right ofqisn−(n+1−i) =i−1. Thus,−σ˜ ∈ S^r_n, and soσ∈ −S˜^r_n.

We have thus shown that for eachσ∈U_Pⁿ, wherer precedesq, either σ∈S^r_n or σ∈ −S˜^r_n. Now consider σ∈Uⁿ_P in whichq precedes r. Then either ˜σ∈S^r_nor ˜σ∈ −S˜^r_n. Hence eitherσ∈S˜^r_norσ∈ −S^r_n.

Corollary2.6. IfP is an adjacent difference property, then

U_Pⁿ=S^r_n(P)∪S˜^r_n(P)∪ −S^r_n(P)∪ −S˜^r_n(P) (2.11) and the cardinality of each set on the right is exactly one-fourth of the cardinality ofUⁿ_P.

Proof. ByLemma 2.2,F_n^r(P)and−F_n^r(P)are empty and by Lemmas2.3 and2.4, the sets on the right are pairwise disjoint and equivalent.

3. A faster algorithm for generating permutations with the SI property

An adaptation of a standard backtracking procedure[2], gives a simple algorithm for generating all permutations in Πn satisfying a property P. This algorithm, which we denote byA0(P)or simplyA0, consists of traversing the following labeled treeT0=T0(P)in preorder:

(i)the root ofT0is marked and labeled with the empty sequence;

(ii)the children of any marked nodevlabeledσare labeledσs1, . . . , σsk, wheres1<···< skare the elements ofNnthat do not appear inσor in any ancestor ofσ;

(iii)a node labeled σ is marked if and only if σ∈UP. Unmarked nodes are leaves.

Clearly,T0has depth at mostn−1. The setUⁿ_P consists of the labels of the marked leaves of depthn−1.

When P is an SI property, a much more efficient algorithm can be obtained by adjoining terms to both sides of the sequences, not just one side as in A0. This new algorithm, calledA1(P)or simply A1, consists of traversing the tree T1 in preorder, and writing the labels of marked leaves with depthn−1 as well as their appropriate symmetries. For any r∈Nn, the treeT1=T1(P)is defined as follows:

(a)every node ofT1is colored either red or yellow, is either marked or unmarked, and has a label consisting of a permutation se- quence of some or all members ofNn;

(b)the root ofT1is red, marked, and has labelr;

(c)ifvis a red, marked node with labelσ, thenvhas red children labeledσs1, σs2, . . . , σsk, wheres1< s2<···< sk are the elements ofNnthat do not appear inσor in the label of any ancestor ofv.

If in addition σ containsq, then v has yellow children labeled s1σ, s2σ, . . . , skσ;

(d)a yellow, marked node with labelσhas yellow children that are labeled as in(c);

x 1

x

12 x

13 x

14

123 x

124 x

132

x

134 x

142 x

143 214 314

x

1243 3124 1324 1342 2134 x

1423 3142 x

1432 2413

Figure3.1

(e)a red node with labelσsiis marked if and only ifσsi∈UP unless i=kandsk=q,σsk is at depthn−1, andπ(m) +π(n−m+1)≥ n+1, whereσ=π(Nn)andmis the least index for whichπ(m) + π(n−m+1)=n+1;

(f)a yellow child with labelσ is marked if and only ifσ∈UP and the number of elements to the right ofqis greater than the num- ber of elements to the left ofr orn−j=i−1 and eitherσ∈F^r_nor π(m) +π(n−m+1)< n+1, whereσ=π(Nn)andmis the least index for whichπ(m) +π(n−m+1)=n+1.

Suppose, for example, thatn=4,r=1,q=4, andP is the “adjacent difference” property, that is, for anyπ∈π(Nn),P(π)is true if and only if no two differences of distinct adjacent terms are equal. ThenT1(P)is as follows(Figure 3.1), where red nodes are denoted by circles, yellow nodes by rectangles, and marked nodes are indicated by an “x” written within the circle or rectangle.

Theorem3.1. For any SI propertyP, S^r_n∪F_n^r=

σ|σis a label of a marked leaf of depthn−1ofT1(P)

(3.1)

and these labels are nonrepeating.

Proof. A nodevwith labelσof T1 is a leaf of depthn−1 if and only if there is a path from the root ofT1tovin which the label of each node on each levelk on the path is a sequenceσof lengthk for whichσ∈UP, andσ=τ1στ2 for someτ1 andτ2. A red child adds an element to the right of the label of its parent, and a yellow child adds an element to the left of the label of its parent. Furthermore, each levelk contains all sequences of lengthkthat belong toUP∪F_n^r.

A yellow node can have only yellow children, and a red node can have a yellow child only when its label containsq. Lettingσidenote the ith term added in order to formσ, we have thatσis the label of leafvof T1of depthn−1 if and only if it is of the form

σn···σn−i+2σ1σ2···σn−i+1, (3.2) whereσ1=r, andσj=qfor somej,i < j≤n−i+1, that is, if and only if for some permutationπ,

σ=π(1)···π(i) =r···π(j) =q···π(n). (3.3) Furthermorevis marked if and only if

(1)it is red, that is,i=1 and hence eithern=j andn−j > i−1 or n=jandπ(m) +π(n−m+1)< n+1 wheremis the least index for whichπ(m) +π(n−m+1)=n+1 or

(2)it is yellow, that is,n−j > i−1 orn−j=i−1 andπ(m) +π(n− m−1)> n+1 andmis defined as before.

But these are exactly the conditions under which σ∈S^r_n∪F_n^r and hence equality of the two sets follows. Finally, note that for any node ofT1 with labelσ, there is only one path from the root tov, and hence the marked leaves ofT1of depthn−1 are distinct.

Now algorithmA1(P)is obtained by traversingT1(P)in preorder. For each marked leaf of depthn−1, with label, sayσ, ifσis not a fixed point, we printσ,−σ, ˜σ, and−σ. If˜ σis a fixed point, we print onlyσand−σ.

IfP is an adjacent difference property, we need not test for fixed points, but simply printσ,−σ, ˜σ, and −σ˜ for each marked leaf of depth n−1 with labelσ.

To achieve parallelism in algorithm A1(P) we use the “manager- worker” technique. The manager generates the upper portion of the tree T1(P), by generating those nodes of fixed depthd, for somed. The man- ager dynamically passes each of these sequences of lengthd to an idle worker, who in turn continues to search for sequences with propertyP that contain the fixed subsequence of length d. The worker returns all such sequences with propertyP to the manager and then waits for an- other subsequence of lengthd. The manager continues to compute sub- sequences of lengthduntil no more such subsequences exist.

4. Costas sequences

The algorithmA1(P)ofSection 3 has been presented in a very general setting. To specialize it to any particular class of symmetry-invariant per- mutations, one need only specify criteria for membership in the setUP

Table4.1

n C(n)

19 10240

20 6464

21 3536

22 2052

23 872

24 ≥8

for the given propertyP. Special cases of interest are for the Costas prop- erty and then-queens propertyQ.

This last section is devoted to describing the work done in applying the algorithm to the generation of Costas sequences, which are used in encoding radar and sonar signals. In this case, it is necessary to generate only one-fourth ofUCsinceCis an adjacent difference property.

We have implemented A1(C) on several platforms over a period of several years, yielding new Costas sequences for various values of n.

Previously, Silverman et al. [3] were able to compute all Costas se- quences of size n≤18, but abandoned the search for larger sequences after predicting that the casen=19 would require more than one year of computer time.

The first two authors of this work initially implementedA1(C)in OC- CAM on an eight T800 transputer system mounted on an IBM PC-AT.

With this(MIMD)implementation, Costas sequences were obtained for n≤20. Subsequently, they implemented it in C on an Intel Paragon, ob- taining all Costas sequences forn=21,n=22, andn=23.

The second two authors implementedA1(PC)in C/MPI on a Super Sparc cluster of 32 workstations, verifying all of the above results. This latter implementation also yielded a new Costas sequence for sizen=24, namely, X = (18,16,10,22,13,24,6,1,2,15,3,5,11,20,23,19,12,4,9,17,14, 21,8,7). Another known Costas sequence of size 24 that results from a construction described in[1]isY= (6,2,4,7,20,21,3,8,18,15,14,12,5,23, 17,24,10,19,9,13,1,16,11,22). The symmetries of the groupG4applied to XandY yield 6 more distinct Costas sequences. We can therefore con- clude that there are at least 8 Costas sequences of size 24.

Table 4.1summarizes the contributions of algorithmA1to known val- ues ofC(n), the number of Costas arrays of sizen.

Even though algorithm A1 is a considerable improvement over A0, it still has exponential computational complexity. Nevertheless, imple- mentations ofA1have been optimal. In each of the implementations we chosed, so that the number of nodes at depth din T1 is several times

greater than the number of processors available. This insures that each of the processors is kept busy. It turns out in fact that our implementa- tions achieved speedups close topwherepis the number of processors.

Furthermore, the only communications necessary are between master and slave and for fixedd, the number of these is polynomial inn. Thus, the communication to computation ratio tends to zero asn→ ∞.

Acknowledgment

This research was supported by grants from the Office of Naval Re- search(ONR)N00014-96-1-1192 and National Science Foundation(NSF) EIA9977071.

References

[1] S. Golomb and H. Taylor,Constructions and properties of Costas arrays, Proc.

IEEE72(1984), 1143–1163.

[2] E. Horowitz, S. Sahni, and S. Rajasekaran,Computer Algorithms C++, Com- puter Science Press, New York, 1996.

[3] J. Silverman, V. Vickers, and J. Mooney,On the number of Costas arrays as a function of array size, Proc. IEEE76(1988), 851–853.

Oscar Moreno: Department of Mathematics and Computer Science, University of Puerto Rico, Rio Piedras, PR 00931-3355, USA

John Ramírez: The Graduate School and University Center, The City University of New York, 365 Fifth Avenue, New York, NY 10016-4309, USA

Dorothy Bollman: Department of Mathematics, University of Puerto Rico, Mayaguez, PR 00681-9018, USA

E-mail address:[email protected]

Edusmildo Orozco: Department of Mathematics, University of Puerto Rico, Mayaguez, PR 00681-9018, USA