\documentclass[11pt]{amsart} %[11pt] %\usepackage[T1]{fontenc} %\usepackage[latin1]{inputenc} \usepackage{amsmath} \usepackage{amssymb} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newcommand{\DEF}{\buildrel {\rm def} \over =} \newcommand{\id}{\mathop{\rm id}} \newcommand{\Bid}{{\id}^\circ} \newcommand{\Bpi}{{\pi}^\circ} \newcommand{\Tpi}{\Bpi_\circ} \newcommand{\xbar}{\overline{x}} \newcommand{\ybar}{\overline{y}} \newcommand{\abar}{\overline{a}} \begin{document} \title{Sorting a bridge hand} %\author[H.~Eriksson et al]{Henrik~Eriksson} \author[H.~Eriksson]{Henrik~Eriksson} \address{NADA, KTH, SE-100 44, Stockholm, Sweden} \email{henrik@nada.kth.se} \author[K.~Eriksson]{Kimmo~Eriksson} \thanks{K.E.: Partially supported by the Swedish Natural Science Council and the Swedish Foundation for Strategic Research.} \address{IMa, M{\"a}lardalens H{\"o}gskola, Box 883, SE-721 23 V{\"a}ster{\aa}s} \author[J.~Karlander]{Johan~Karlander} \author[L.~Svensson]{Lars~Svensson} \author[J.~W{\"a}stlund]{Johan~W{\"a}stlund} \address{Department of Mathematics, KTH, SE-100 44, Stockholm, Sweden} % \keywords{} % \subjclass{Primary: ; Secondary: } \date{} \begin{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. %The minimum number of block moves needed to get from one species to the %other is a parameter that biologists find of interest. 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 $\lfloor (2n-2)/3 \rfloor$ for $n\ge 9$. For the reverse permutation, we give an exact expression for the number of moves needed, namely $\lceil (n+1)/2 \rceil$. 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. \end{abstract} \maketitle \section{Introduction}\noindent 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 \ref{sc:values}. 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 \ref{sc:values}. 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 \cite{BP}, 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 \cite{BP} 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$. \section{Notation and definitions} \noindent We will denote a permutation in $S_n$ by its sequence of permuted numbers within brackets: \[ \pi = [\pi_1\ \pi_2\ \dots\ \pi_{n-1}\ \pi_n]. \] For any three cut points $0\le i\pi_{k+1}$. Although for a toric permutation the notion of descent makes no sense, the {\em number of descents} still has meaning; it is easy to see that if $\pi$ and $\tau$ represent the same toric permutation, then $\pi$ and $\tau$ have the same number of descents. \begin{lemma} The number of descents in a permutation can decrease by at most two in a block move. \end{lemma} \begin{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: \[ [\dots \ a\ b\ \dots \ c\ d\ \dots \ e\ f \dots], \] where $a>b$, $c>d$ and $e>f$, and where all three descents are broken by a move, giving \vspace{-2mm} \[ [\dots \ a\ d\ \dots \ e\ b\ \dots \ c\ f \dots], \] with no new descents, so that $ax_\ell$, for otherwise criterion (\ref{eq:2-inv}) applies to $0\ x_1\ \dots\ x_\ell\ 1$. By the minimality condition on the length of $0\dots 1$, we know that $\xbar_1$ is not in that interval and thus a 1-move $$0|x_1\ x_2\dots x_\ell\ |1\dots |\xbar_1$$ is possible, after which we have $$x_1\ x_2\dots x_\ell\ \xbar_1.$$ Now unless $x_1>x_2>x_\ell$, criterion (\ref{eq:2-inv}) yields the lemma. Thus we need only assume $\pi= 0\ x_1\ x_2 \dots x_\ell\ 1\dots$ with $x_1>x_2>x_\ell$ and $\ell \ge 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$. \subsection{The case for $x_2=x_1-1$} The minimality condition on $0\dots 1$ means that the situation $0\dots x\dots \xbar\dots 1$ cannot occur. In the case there is an $x$ such that $$0\ x_1\ x_2 \dots x\dots 1\dots \xbar \dots,$$ a 1-move $0\ x_1 |\ x_2\dots x|\dots 1\dots |\xbar \dots$ would lead to $0\ x_1\dots 1\dots x_2 \dots$, after which a 2-move is possible according to criterion (\ref{eq:2-move}). The only other possibility is that, for each $x$ inside $x_2 \ldots1$, $\xbar$ is further left in $0 \ldots 1$. By letting $x$ be $x_3$, $x_4$, etc. consecutively, we see that $0 x_1 x_2 \ldots x_{\ell}$ must be a reversed consecutive sequence. In this case either $x_{\ell} =2$ or $x_{\ell} >2$ with $x_i \ne 2$ for $i \le \ell$. For the subcase where $x_{\ell} = 2$, we have, by the assumed non-reducibility, that the value $1$ is not followed by $\xbar_1$ . Moreover, 1 is not followed by 0 since $\pi\neq w_0$. Hence there is a 1-move $$0|x_1\dots 2|1 \xbar|\dots x$$ leading to $1\xbar\dots 2\dots x$, and criterion (\ref{eq:2-move}) applies. For the remaining subcase, we have that $x_\ell>2$. Since $0\ x_1\ x_2 \dots x_{\ell-1} x_{\ell}$ is a reverse consecutive sequence, 2 must be to the right of $x_{\ell}$. The lack of bonds implies $2 < x_{\ell + 2} < x_{\ell}$. Hence, the 1-move $$ 0\ | x_1 \ldots x_{\ell-1} x_{\ell} 1| x_{\ell + 2} \ldots | 2 \ldots $$ leads to $$ 0 \ x_{\ell + 2} \ldots x_{\ell} \ 1\ 2 \ldots$$ to which criterion (\ref{eq:2-inv}) applies. \subsection{The case for $x_1 > x_2 -1$ } Note that $\underline{x}_1 \neq x_2$. If $\underline{x}_1 $ is to the right of 1, criterion (1) applies to $0 x_1 \dots 1 \dots \underline{x}_1$. If $\underline{x}_1 $ is to the left of 1, then let $k \ge 2 $ be the smallest $k$, $k \in \{ 2, \ldots, \ell -1 \}$, such that $$ x_1 + k - 1 > x_2 + k - 2 > x_3 + k - 3 > \ldots > x_k > x_{\ell}. $$ The minimality condition on $0 \ldots 1$ implies that $\xbar_k$ is to the right of 1, so there is a 1-move $$ 0|x_1\dots x_\ell|1\dots |\xbar_k, $$ resulting in a permutation containing the sequence $$ 0 \ 1\ \dots x_k\ x_{k+1}\dots x_\ell\ \xbar_k.$$ Now, either (a) $x_k > x_{\ell} > x_{k+1}$, (b) $x_{k+1} > x_k > x_{\ell}$, or (c) $ x_k > x_{k+1} > x_{\ell}.$ 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 $\xbar_{k+1} = x_k$, which we can split by a 1-move $$0|x_1\dots x_k|x_{k+1}\dots\underline{x}_1|\dots 1.$$ Now criterion (\ref{eq:2-move}) can be used on $x_{k+1}\dots x_{k-1}x_k \dots \xbar_{k-1}$. Note that by the minimality of $0\dots 1$, the value $\xbar_{k-1}$ must occur to the right of 1. This completes the proof of Lemma \ref{lm:3-in-2}. \end{proof} \section{The bridge player's problem and $d(n)$ for $n\le 15$} \label{sc:values} The values of $d(n)$ for $n\leq 10$ were calculated by computer, by breadth-first construction of the Cayley graph (which has on the order of $n^3\cdot 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)=\lceil(n+1)/2\rceil$ cannot allow a 2-move or a 1-move followed by a 3-move. For $n\le 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 $\lceil(n+1)/2\rceil$ 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 \ref{lm:3-in-2} says in effect that $d(n+3)\le d(n)+2$, so we have $d(14)\le 8$ and $d(15)\le 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 $\lfloor (n-1)/2 \rfloor$ 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 \ref{lm:3-in-2}, that $\lfloor (n-1)/2 \rfloor$ 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. \begin{theorem} If $n+1$ cards are arranged cyclically, then the suits can be grouped together in at most $\lfloor \frac{n-1}{2} \rfloor$ block moves. \end{theorem} \begin{proof} We will use induction on $n$. The statement is obviously true for $n\leq 2$. A \emph{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: \[ \spadesuit |\dots \heartsuit |\spadesuit \dots |\heartsuit \] Cutting at the indicated places gives two bonds, and the induction is complete. \end{proof} \begin{corollary} For any array of $n$ not necessarily different objects, $\lfloor \frac{n-1}{2} \rfloor$ block moves are sufficient to group like objects together. This bound is sharp. \end{corollary}\noindent Hence, a bridge hand can be suit separated in at most 6 block moves, and this bound is attained if two suits alternate. % \[ \spadesuit \heartsuit \spadesuit \heartsuit %\spadesuit \heartsuit \spadesuit \heartsuit \spadesuit \heartsuit %\spadesuit \heartsuit \spadesuit. %\] 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. \section{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 \cite{C}. 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 $\lceil \frac{n}{3} \rceil$ moves and at most $\lfloor\frac{2n-2}{3}\rfloor$ 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 $\lceil\frac{n+1}{2}\rceil$. 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\le 9$, about 71\% live on level $\lceil\frac{n+1}{2}\rceil$, about 29\% on the level below and no permutations occupy lower levels! Hence, after contracting bonds in a random gene permutation you can use $\lceil\frac{n+1}{2}\rceil$ to estimate its transposition distance; judging from the pattern for small $n$, it is unlikely that you will be off by more than one. % %However, gene permutations are not really random, so they may be closer %to the lower bound $\lceil\frac{n}{3} \rceil$. %The lower bound applies only to a product of 3-moves. If there are thousands %of genes and all breakpoints are equally probable, %then among the first hundred %block moves, probably most will be 3-moves. So, in this biologically %interesting case, we are in fact close to the lower bound. A more %typical situation, however, is when breakpoints occur with much higher %probability at some {\em hot spots}. So after all, the percentages for %random permutations may well apply to gene permutations also. \begin{thebibliography}{ABC} \bibitem{BP} V. Bafna and P. Pevzner, Sorting by transpositions, {\em SIAM J.Discrete Math.} {\bf 11 } (1998), 224--240. \bibitem{C} A. Caprara, Sorting by reversals is difficult, {\em Proc. RECOMB '97}, ACM Press, 1997. \bibitem{Hu} A. Hultman, Toric permutations, M.Sc. thesis, Dept. of Mathematics, KTH, Stockholm, Sweden, 1999. \bibitem{St} J. E. A. Steggall, On the number of patterns which can be derived from certain identities, {\em Messenger Math.} {\bf 37 } (1907), 56--61. \end{thebibliography} \end{document}