SORTING A BRIDGE HAND

HENRIK ERIKSSON, KIMMO ERIKSSON, JOHAN KARLANDER, LARS SVENSSON, AND JOHAN WÄSTLUND

Abstract. Sorting a permutation by block moves is a task that every bridge player has to solve every time she picks up a new hand of cards. It is also a problem for the computational biologist, for block moves are a fundamental type of mutation that can explain why genes common to two species do not occur in the same order in the chromosome.

It is not known whether there exists an optimal sorting procedure running in polynomial time. Bafna and Pevzner gave a polynomial time algorithm that sorts any permutation of length n in at most 3n/4 moves. Our new algorithm improves this to ⌊(2n − 2)/3⌋ for n ≥ 9. For the reverse permutation, we give an exact expression for the number of moves needed, namely ⌈(n+1)/2⌉. Computations of Bafna and Pevzner up to n = 10 seemed to suggest that this is the worst case; but as it turns out, a first counterexample occurs for n = 13, i.e. the bridge player’s case.

Professional card players never sort by rank, only by suit. For this case, we give a complete answer to the optimal sorting problem.

1. Introduction

Considering the vast literature on bridge bidding and play, it is only right that the phase preceding the bidding should receive its proper analysis. Each player is dealt thirteen cards face-down on the table, picks them up, has a quick look and starts rearranging the hand. Most bridge players use block transpositions to rearrange their thirteen cards in some preferred order. Empirically, from diligent bridge playing or computer simulations, one finds that most hands can be sorted in six moves while about 30% need seven moves. One of these is the reverse permutation, intuitively felt to be the worst case. It is a real challenge to sort the permutation [13 12 11 10 9 8 7 6 5 4 3 2 1] in seven block moves, and the fearless reader is invited to take on that challenge before reading further! It is hardly feasible to let the computer check all 13! permutations, so some analysis is needed to find out what is actually the worst case. The unexpected answer will be given in section ??.

When one plays a card from a sorted bridge hand, one’s opponents may draw some information from the position of the card. Therefore, professional card players never order their cards by rank, only by suit. The corresponding optimal sorting problem is easier and gets a complete analysis in section ??.

K.E.: Partially supported by the Swedish Natural Science Council and the Swedish Foundation for Strategic Research.

2 H. ERIKSSON, K. ERIKSSON, J. KARLANDER, L. SVENSSON, AND J. WÄSTLUND

It turns out that the bridge player can always separate suits in six block moves.

Scientific applications might be found in the field of bioinformatics. For the details, we refer to Bafna and Pevzner [?], but the gist of the matter is that block transpositions occur in gene sequences as rare mutation events. The genome breaks in three places and the two middle pieces are glued back transposed.

Bafna and Pevzner [?] devised a sorting algorithm with a worst case performance of about 3n/4 block moves. Our block move sorting algorithm has a better worst case performance, asymptotically 2n/3.

2. Notation and definitions

We will denote a permutation in S_{n} by its sequence of permuted numbers within brackets:

π = [π_{1} π_{2} … π_{n−1} π_{n}].

For any three cut points 0 ≤ i < j < k ≤ n, define the block move σ_{ijk} by

σ_{ijk} = [1 … i j+1 … k i+1 … j k+1 … n].

This may also be called a block transposition, as two adjacent blocks have been transposed.

Composition of permutations is defined as action to the right:

π · σ_{ijk} = [π_{1} … π_{i} π_{j+1} … π_{k} π_{i+1} … π_{j} π_{k+1} … π_{n}].

For convenience, we introduce symbols for two permutations of fundamental importance, the identity and the reverse permutation:

id =^{def} [1 2 … n−1 n] and w_{0} =^{def} [n n−1 … 2 1].

2.1. Toric model of permutations. We can extend an ordinary permutation π to a circular permutation π^{∘} by inserting an extra element 0 as both predecessor of π_{1} and successor of π_{n}, and taking the equivalence class under cyclic shifts. We write

π^{∘} = 0 π_{1} π_{2} … π_{n}

where the absence of brackets indicates an equivalence class under cyclic shifts. For example, 0312 = 3120 = 1203 = 2031. From a circular permutation π^{∘}, we uniquely retrieve the ordinary permutation π by removing the element 0 and letting its successor be the first element of π.

A block move on π has an effect on π^{∘} that is easy to state: The circle is cut into three segments which are then glued together in the other possible order. Although this is a slightly nicer setting for our original sorting problem we will go one step further and consider toric permutations, which are circular in values as well as in positions. An m-step cyclic value shift of π^{∘} is defined as

m+π^{∘} = m m+π_{1} m+π_{2} … m+π_{n} (mod n+1)

and the equivalence class of π^{∘} under such value shifts is the toric permutation π_{∘}^{∘}.

The point of considering equivalence under value shifts is that a strategy for block sorting π^{∘} will work also for m + π^{∘}: If a move sequence takes π^{∘} to id^{∘}, then the same sequence of moves takes m+π^{∘} to m+id^{∘}; and m+id^{∘} = id^{∘}, so the sorting is done! For example, if π = [3 1 2], then the representatives of the toric permutation are:

\begin{aligned}π^{∘} & = 0312 \\ 1+π^{∘} & = 1023 \\ 2+π^{∘} & = 2130 \\ 3+π^{∘} & = 3201 \end{aligned}

So [312]_{∘}^{∘} = [231]_{∘}^{∘} = [213]_{∘}^{∘} = [132]_{∘}^{∘} and therefore a block sorting strategy for [312] can be translated into a strategy for any of the other three permutations.

It is convenient to let \overline{x} denote the numerical successor of x in any representative of a toric permutation, i.e. \overline{x} = x+1 (mod n+1). Similarly, we let \underline{x} = x−1 (mod n+1). An occurrence of x\overline{x} is called a bond, and it is clear that bonds need never be broken in an optimal sorting strategy which is to end with the identity permutation. An occurrence of \overline{x}x is called an anti-bond. Circularity in positions and values must always be taken into account; thus 314052 has one bond (23) and one anti-bond (05).

In a representative of a toric permutation, we say that an ordered triple of values x … y … z is positively oriented if either x < y < z or y < z < x or z < x < y.

The justification for the term toric is the following. An ordinary permutation has a geometric representation as a square matrix with n rows and n columns and with n dots, one in each row and each column. Joining the two vertical sides of the square, we get a cylinder representing a circular permutation. Joining also the two horizontal sides, we get a torus representing a toric permutation. Although toric permutations seem to us a natural construction, we have not found any previous mention in the literature. An equivalent class of objects, infinite periodic patterns built up from permutation matrices, was invented and enumerated in 1907 by Steggall [?], but with no other applications or further considerations. In a very recent M.Sc. thesis at KTH, Hultman [?] improves the enumeration argument and also discusses some other aspects of toric permutations.

3. The Cayley graph of block transpositions

The symmetric group S_{n} is generated by the set of all block moves. Hence we can define the so called Cayley graph, with vertex set S_{n} and a directed edge labeled σ_{ijk} from any π ∈ S_{n} to π · σ_{ijk}. A block sorting strategy for π is a directed path from π to id. Reading the labels of the path, we get the identity πσ_{1}σ_{2} ⋯ σ_{ℓ} = id.

Let d(π) denote the distance from id to π in the Cayley graph, i.e. the minimal number of block moves needed to sort π.

3.1. Inverses. The inverse of a block move is also a block move:

σ_{ijk}^{−1} = σ_{irk},

where r = i + k − j. This means that the block sorting strategy for π can be regarded as a factorization of π into block moves: π = σ_{ℓ}^{−1} ⋯ σ_{2}^{−1}σ_{1}^{−1}. We can conclude that d(π) is in fact the length of the shortest word for π in the alphabet of block moves. Since π^{−1} = σ_{1}σ_{2} ⋯ σ_{ℓ}, we can also conclude that d(π^{−1}) = d(π).

Note that the inverse is also well defined for toric permutations, for it is easy to see that if π and τ represent the same toric permutation, then π^{−1} and τ^{−1} represent the same toric permutation.

3.2. The undirected Cayley graph and the toric graph. We will let any pair of inversely directed edges in the Cayley graph merge into one undirected edge, and thus obtain an undirected graph. By merging vertices representing the same toric permutation, we obtain the toric graph. This seems to be the correct mathematical object for our investigation.

[figure: [123]_{∘}^{∘}; [132]_{∘}^{∘}; [321]_{∘}^{∘}; [1234]_{∘}^{∘}; [1243]_{∘}^{∘}; [1342]_{∘}^{∘}; [2143]_{∘}^{∘}; [1432]_{∘}^{∘}; [2413]_{∘}^{∘}; [3142]_{∘}^{∘}; [4321]_{∘}^{∘}]

Figure 1. The toric graphs for n = 3 and n = 4.

3.3. The diameter of the Cayley graph. The diameter of a graph is the maximal distance between two vertices. Since the Cayley graph looks exactly the same when seen from any vertex, its diameter is the maximal distance from id to any π. This number is equal to the diameter of the toric graph, and, of course, also to the number of block moves needed, in the worst case, to sort a permutation. We will denote this diameter, for a given n, by

d(n) =^{def} max_{π∈S_{n}}{d(π)}.

Bafna and Pevzner [?] observed that d(n) = ⌈\frac{n+1}{2}⌉ for 3 ≤ n ≤ 10. When we started working on this problem we assumed that this expression for d(n) would hold for all n ≥ 3. Bafna and Pevzner also proved that the value of d(n) lies in the interval ⌈\frac{n−1}{2}⌉ ≤ d(n) ≤ ⌊\frac{3n}{4}⌋.

Our agenda in this paper is the following:

1. For the reverse permutation we find an exact value: d(w_{0}) = ⌈\frac{n+1}{2}⌉ for n ≥ 3, which gives an improved general lower bound: d(n) ≥ ⌈\frac{n+1}{2}⌉.

2. We improve the upper bound to d(n) ≤ ⌊\frac{2n−2}{3}⌋.

3. By a combination of computer assisted computations and theoretical arguments, we are able to determine d(n) for n ≤ 15 (Table 1).

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ d(n) & 0 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 & 7 & 8 & 8 & 9 \end{matrix}

Table 1. Known values of d(n).

Note that our upper bound d(n) ≤ ⌊\frac{2n−2}{3}⌋ is sharp for 9 ≤ n ≤ 15. Our computer experiments suggest, however, that the patterns that are especially difficult to block sort for n = 13 and n = 15 cease to be difficult for larger n. Hence, our new conjecture is that d(n) = ⌈\frac{n+1}{2}⌉ for all n ≥ 3 except for n = 13 and n = 15.

4. An improved lower bound and the reverse permutation

Recall that a descent in a permutation π is an occurrence of π_{k}π_{k+1}, such that π_{k} > π_{k+1}. Although for a toric permutation the notion of descent makes no sense, the number of descents still has meaning; it is easy to see that if π and τ represent the same toric permutation, then π and τ have the same number of descents.

Lemma 4.1. The number of descents in a permutation can decrease by at most two in a block move.

Proof. Obviously, the number of descents can change by at most three in every move. We will see that a decrease by three is in fact impossible, since it would require a permutation of the following form:

[… a b … c d … e f …],

where a > b, c > d and e > f, and where all three descents are broken by a move, giving

[… a d … e b … c f …],

with no new descents, so that a < d, e < b and c < f. Together, the six inequalities imply that

a < d < c < f < e < b < a,

which is absurd. The argument remains valid if b = c, d = e or f = a.

4.1. An optimal sorting algorithm for w_{0}. Now we return to the bridge player, faced with the problem of reversing the order of her cards using only seven block moves. For simplicity, we illustrate the solution for n = 9 cards, which easily extends to any n cards. |9876|54|321 → 5|4987|63|21 → 56|3498|72|1→567|2349|81|→|5678|1234|9→123456789

Theorem 4.2. For n ≥ 3, the reverse permutation w_{0} can be sorted in ⌈\frac{n+1}{2}⌉ block moves, and this is optimal.

Proof. It is sufficient to give an algorithm for odd n = 2k +1 using k +1 moves, for if we have an even n = 2k, we can use the algorithm for n = 2k+1, forgetting about one of the elements.

Algorithm: We can sort w_{0} = [n … 1 0] by k + 1 moves of the same type: a block of size two is moved k steps to the left. First [k+1 k] is moved to the far left, then [k+2 k−1] is inserted in the middle of the block last moved etc. The last pair to be moved is [n0], after which the permutation will be [k+1 … n 0 … k], a representative of the toric identity permutation.

Optimality: w_{0} has n−1 descents, while id has no descent. It is easy to see that any first move from w_{0} can decrease the number of descents by just one. The same holds for any last move leading to id. By the above lemma, each intermediate move decreases the number of descents by at most two. Hence, at least (n − 3)/2 moves must be made between the first and the last move (but for n = 2, the first move is also the last).

5. An improved upper bound

In this section, we will prove a new upper bound on d(n). The main work will be to prove the following lemma.

Lemma 5.1. Let π be any permutation other than w_{0}. Then we can find block moves σ and τ such that one of πστ, σπτ, and στπ has at least three bonds.

We defer the proof of the lemma until after the statement and proof of the main theorem:

Theorem 5.2. An upper bound on the number of block moves needed to sort a permutation is d(n) ≤ ⌊\frac{2n−2}{3}⌋ for n ≥ 9.

Proof. First, we will prove that d(π) ≤ 2 + d(n − 3) for any permutation with n ≥ 9. If π = w_{0}, this is a consequence of Theorem ??. If π is any permutation other than w_{0}, then one of the three cases in Lemma ?? applies.

In the case where σπτ has three bonds, we know that d(σπτ) ≤ d(n − 3), for bonds can be regarded as single symbols. By writing π = σ^{−1}σπττ^{−1} we get

d(π) ≤ d(σ^{−1}) + d(σπτ) + d(τ^{−1}) ≤ 1 + d(n − 3) + 1.

The two other cases are similar.

But if for an arbitrary permutation d(π) ≤ 2+d(n−3), then the definition of d(n) implies d(n) ≤ 2 + d(n − 3), for n ≥ 9. Since Table 1 shows that d(n) = ⌊(2n − 2)/3⌋ for 9 ≤ n ≤ 11, the theorem follows by induction.

Proof of Lemma ??. If there is already a bond in π, then getting two more bonds in two moves is trivial, so we can assume that π is bondless. As we will see below, all permutations other than w_{0} fall into one of several categories, for each of which we can construct the required move or moves. In fact, the proof of Lemma ?? amounts to an algorithm for sorting any permutation by block moves. We will use the toric model of permutations throughout the proof, which occupies the remainder of Section 5.

5.1. Criteria for existence of 2-moves. Given a permutation π, we define a k-move to be a block move σ such that πσ has k more bonds than π. A block move σ is a k-move to the left if σπ has k more bonds than π.

A 2-move is possible in π if the toric permutation π_{∘}^{∘} contains a segment of the form x … y\overline{x} … \overline{y}, since the block move defined by cutting at the indicated places

x| … y|\overline{x} … |\overline{y} , (1)

gives x\overline{x} … y\overline{y} with two new bonds. We allow the possibility that x = \overline{y}. A 2-move to the left is possible in π if the toric permutation π_{∘}^{∘} has a segment of the form

xy … z\overline{x}, (2)

where x, y, z are positively oriented. Here we allow the possibility that y = z. It is easy to verify that the criteria (??) and (??) are transformed into each other if the roles of values and positions are interchanged.

If either criterion (1) or (2) is satisfied, then getting a following 1-move is trivial, resulting in the desired three bonds.

5.2. Reducibility. We say that a toric permutation is reducible if, in some suitable representation π and for some 0 < k < n, the segment 0 … π_{k} contains all values 0, …, k and the segment π_{k} … π_{n} contains all values k, …, n. In particular, π_{k} = k must then be true.

Here we show that the lemma holds in the reducible case. We can reduce a reducible permutation to a smaller toric permutation by contracting the segment π_{k} … π_{n} 0 to a single symbol 0. If the reduced permutation is not a reverse permutation, then we can use induction to find the required moves yielding the lemma. On the other hand, if it does reduce to a reverse permutation, we instead contract the segment 0 … π_{k} to 0. Again, if the reduced permutation is not a reverse permutation, then we can use induction to find the required moves yielding the lemma. In the remaining case where both contractions result in a reverse permutation, we must have

π = [0 k−1 k−2 … 1 k n n−1 … k+1],

and after the 1-move

0 k−1 | k−2 … 1 k n | n−1 … k+1 |

(bonding n0), criterion (??) applies to k−1 n−1 … 1 k yielding the lemma. For example, in 0432159876 we first try to contract 598760, but this results in 04321, which is a reverse permutation. Then we contract the first six values and obtain 09876, which is interpreted as 04321, another reverse permutation. Finally, a 1-move produces 0487632159, and here criterion (??) applies to 48 … 15.

5.3. All other possibilities considered. Here we show that the lemma holds whenever the toric permutation π_{∘}^{∘} is bondless, non-reducible, and does not satisfy either criterion (1) or (2) for 2-moves. We can find a value x in a representative of π_{∘}^{∘} such that the length of x … \overline{x} is minimum. Specifically, we choose that representative π with x = 0 and initial sequence 0 … 1 of this minimum length. The absence of bonds excludes the extreme case 01 and the absence of 2-moves prohibits 0a1, as a could be moved to bond with \overline{a}, while allowing 0 to bond with 1.

Let this permutation be denoted as π = 0 x_{1} x_{2} … x_{ℓ} 1 …, with ℓ ≥ 2. We must have x_{1} > x_{ℓ}, for otherwise criterion (??) applies to 0 x_{1} … x_{ℓ} 1. By the minimality condition on the length of 0 … 1, we know that \overline{x}_{1} is not in that interval and thus a 1-move

0|x_{1} x_{2} … x_{ℓ} |1 … |\overline{x}_{1}

is possible, after which we have

x_{1} x_{2} … x_{ℓ} \overline{x}_{1}.

Now unless x_{1} > x_{2} > x_{ℓ}, criterion (??) yields the lemma. Thus we need only assume π = 0 x_{1} x_{2} … x_{ℓ} 1 … with x_{1} > x_{2} > x_{ℓ} and ℓ ≥ 3. There are two cases that must be treated quite differently: Either x_{2} = x_{1}−1 (an anti-bond) or x_{2} < x_{1} − 1.

5.4. The case for x_{2} = x_{1} − 1. The minimality condition on 0 … 1 means that the situation 0 … x … \overline{x} … 1 cannot occur. In the case there is an x such that

0 x_{1} x_{2} … x … 1 … \overline{x} …,

a 1-move 0 x_{1}| x_{2} … x| … 1 … |\overline{x} … would lead to 0 x_{1} … 1 … x_{2} …, after which a 2-move is possible according to criterion (??). The only other possibility is that, for each x inside x_{2} … 1, \overline{x} is further left in 0 … 1. By letting x be x_{3}, x_{4}, etc. consecutively, we see that 0x_{1}x_{2} … x_{ℓ} must be a reversed consecutive sequence. In this case either x_{ℓ} = 2 or x_{ℓ} > 2 with x_{i} ≠ 2 for i ≤ ℓ.

For the subcase where x_{ℓ} = 2, we have, by the assumed non-reducibility, that the value 1 is not followed by \overline{x}_{1} . Moreover, 1 is not followed by 0 since π ≠ w_{0}. Hence there is a 1-move

0|x_{1} … 2|1\overline{x}| … x

leading to 1\overline{x} … 2 … x, and criterion (??) applies.

For the remaining subcase, we have that x_{ℓ} > 2. Since 0 x_{1} x_{2} … x_{ℓ−1}x_{ℓ} is a reverse consecutive sequence, 2 must be to the right of x_{ℓ}. The lack of bonds implies 2 < x_{ℓ+2} < x_{ℓ}. Hence, the 1-move

0 |x_{1} … x_{ℓ−1}x_{ℓ}1|x_{ℓ+2} … |2 …

leads to

0 x_{ℓ+2} … x_{ℓ} 1 2 …

to which criterion (??) applies.

5.5. The case for x_{1} > x_{2} − 1. Note that \underline{x}_{1} ≠ x_{2}. If \underline{x}_{1} is to the right of 1, criterion (1) applies to 0x_{1} … 1 … \underline{x}_{1}. If \underline{x}_{1} is to the left of 1, then let k ≥ 2 be the smallest k, k ∈ {2, …, ℓ − 1}, such that

x_{1} + k − 1 > x_{2} + k − 2 > x_{3} + k − 3 > … > x_{k} > x_{ℓ}.

The minimality condition on 0 … 1 implies that \overline{x}_{k} is to the right of 1, so there is a 1-move

0|x_{1} … x_{ℓ}|1 … |\overline{x}_{k},

resulting in a permutation containing the sequence

0 1 … x_{k} x_{k+1} … x_{ℓ} \overline{x}_{k}.

Now, either (a) x_{k} > x_{ℓ} > x_{k+1}, (b) x_{k+1} > x_{k} > x_{ℓ}, or (c) x_{k} > x_{k+1} > x_{ℓ}. Inequality (a) is impossible by the definition of k. Inequality (b) permits criterion (2) and thus a 2-move to the left. From the way that k was chosen, for inequality (c) we must have an anti-bond \overline{x}_{k+1} = x_{k}, which we can split by a 1-move

0|x_{1} … x_{k}|x_{k+1} … \underline{x}_{1}| … 1.

Now criterion (??) can be used on x_{k+1} … x_{k−1}x_{k} … \overline{x}_{k−1}. Note that by the minimality of 0 … 1, the value \overline{x}_{k−1} must occur to the right of 1.

This completes the proof of Lemma ??.

6. The bridge player’s problem and d(n) for n ≤ 15

The values of d(n) for n ≤ 10 were calculated by computer, by breadthfirst construction of the Cayley graph (which has on the order of n^{3} · n! edges). We will now describe how we determined the values d(11) = 6, d(12) = 7, d(13) = 8, d(14) = 8 and d(15) = 9. A minimal counterexample to our working conjecture d(n) = ⌈(n + 1)/2⌉ cannot allow a 2-move or a 1-move followed by a 3-move. For n ≤ 13, a computer search listed all toric permutations satisfying this restriction; there are not many of them. For each one of these candidates we have checked by computer if they can be sorted in ⌈(n + 1)/2⌉ moves. This is indeed the case for n = 11, which proves the values d(11) = 6 and d(12) = 7. To our surprise, for n = 13 a counterexample was found: the permutation

[4 3 2 1 5 13 12 11 10 9 8 7 6],

and a few others, need 8 block moves. This means that in the worst case, the bridge player will need eight block moves to sort her hand.

Lemma ?? says in effect that d(n + 3) ≤ d(n) + 2, so we have d(14) ≤ 8 and d(15) ≤ 9. For n = 14, the reverse permutation shows that equality holds. For n = 15, the permutation

[4 3 2 1 5 15 14 13 12 11 10 9 8 7 6]

takes 9 block moves.

One can also consider other sorting problems. Some bridge players only want the cards within each suit sorted without regard to the order of the suits. However, this does not change the worst case, as we may get thirteen cards in a single suit. (Bridge players would not call this a “worst case”.) A different problem occurs if we demand only that all cards in a suit be grouped without concern for the order of the cards within a suit. We invite the reader to verify that if only two suits are present, then in a hand of n cards, the suits can be grouped together in at most ⌊(n − 1)/2⌋ moves. If cards of the different suits alternate, then this bound is attained.

We will show, using some of the ideas of the proof of Lemma ??, that ⌊(n − 1)/2⌋ moves suffice even when there are more than two suits. For simplicity, we use the circular model. To pass from an ordinary hand to a circular arrangement, we add the joker as predecessor of the first card and successor of the last one. The added card is included in the n + 1 count below.

Theorem 6.1. If n + 1 cards are arranged cyclically, then the suits can be grouped together in at most ⌊\frac{n−1}{2}⌋ block moves.

Proof. We will use induction on n. The statement is obviously true for n ≤ 2. A bond will now mean two consecutive cards from the same suit. We can assume that, to begin with, there are no bonds. Furthermore, we can assume that there is at most one “singleton” (only card in its suit), since if there is more than one singleton, the problem becomes at least as difficult as the problem where we replace the singletons by a single suit. We now find a pair of cards from the same suit, such that one of the two segments between these cards does not contain two cards from the same suit, and moreover does not contain the possible singleton. (Note that this is always possible!) Since these two cards, say spades, are not consecutive, the predecessor of the last one, say a heart, must belong to the same suit as a card not in the same segment between the two spades. The situation must be:

♠| … ♡|♠ … |♡

Cutting at the indicated places gives two bonds, and the induction is complete.

Corollary 6.2. For any array of n not necessarily different objects, ⌊\frac{n−1}{2}⌋ block moves are sufficient to group like objects together. This bound is sharp.

Hence, a bridge hand can be suit separated in at most 6 block moves, and this bound is attained if two suits alternate.

One can also demand that the suits should occur in a specified order, without paying attention to the order of the cards within a suit. Then the original sorting problem becomes a special case, so it is perhaps unreasonable to ask for a simple solution to this problem.

7. Discussion

According to molecular biologists, there are two fundamental types of rearrangement events occuring in DNA: block moves and block reversals. It would be desireable with an efficient algorithm for finding the minimal number of such events between two genomes. No such algorithm is known. For the case of (unsigned) block reversals only, the problem has been shown to be NP-complete [?]. Block moves seem to behave somewhat better than, and in our opinion there is still good hope of finding an exact algorithm that runs in polynomial time.

The relative proportion between the two types of events is not known. Our results could be useful in cases where block moves dominate. Typically, genes common to two species often come in largely the same order in both genomes. In other words, there is an abundance of bonds in the permutation. In our analysis, we first contract bonded genes, and without even looking at the resulting no-bonds permutation, we can state that sorting by block moves must take at least ⌈\frac{n}{3}⌉ moves and at most ⌊\frac{2n−2}{3}⌋ moves. In the interval between these bounds, what is the distribution of random permutations?

Computer runs indicate that a large majority of random permutations live at or very near the level occupied by w_{0} in the Cayley graph, which is level ⌈\frac{n+1}{2}⌉. In fact, as n grows, the distribution of permutations on the top levels appears to converge to some limit distribution (one for odd n and one for even n). For odd n we find about 32% of all permutations on the highest level, about 53% on the level below, and about 14% two levels below. The last percent is spread out in a distribution rapidly decreasing with level index.

Such a biased distribution is typical not only for block sorting distance, but for just about any distance measure on permutations based on a set of legal moves. The explanation is that at a low level, the proportion of permutations at this level or below is so small that the vast majority of permutations that can be reached by one move will belong to the level above.

The statistics for random permutations with no bonds is even more biased. For odd n ≤ 9, about 71% live on level ⌈\frac{n+1}{2}⌉, about 29% on the level below and no permutations occupy lower levels! Hence, after contracting bonds in a random gene permutation you can use ⌈\frac{n+1}{2}⌉ to estimate its transposition distance; judging from the pattern for small n, it is unlikely that you will be off by more than one.

References

[1] V. Bafna and P. Pevzner, Sorting by transpositions, SIAM J.Discrete Math. 11 (1998), 224–240.

[2] A. Caprara, Sorting by reversals is difficult, Proc. RECOMB ’97, ACM Press, 1997.

[3] A. Hultman, Toric permutations, M.Sc. thesis, Dept. of Mathematics, KTH, Stockholm, Sweden, 1999.

[4] J. E. A. Steggall, On the number of patterns which can be derived from certain identities, Messenger Math. 37 (1907), 56–61.

NADA, KTH, SE-100 44, Stockholm, Sweden

E-mail address: henrik@nada.kth.se

IMa, Mälardalens Högskola, Box 883, SE-721 23 Västerås

Department of Mathematics, KTH, SE-100 44, Stockholm, Sweden