Hand sort

I was unable to find an analytic or closed-form expression for the solution to this problem, so I’ll present an old fashioned brute-force solution. The idea is simple:

1. Enumerate all possible hands
2. For each hand, enumerate all possible moves that consist of moving some group of adjacent cards to somewhere else in the hand.
3. If any such move succeeds in sorting the hand, mark the hand as “good”.
4. Once we’re done, count all “good” hands and divide that by the total number of hands

Simple, right? I’d like to point out is that this is not an approximate solution; there is no simulation involved. I’m counting all the possible scenarios, so this approach produces the exact answer. The only problem is that there are a lot of hands to check, and the bigger the hands get, the longer it takes to check them, since there are more possible moves. Successfully solving this problem requires coding it up in a way that a computer can find the solution in a reasonable amount of time. In order to make this work, I used several tricks to reduce the computation required:

• We don’t have to enumerate all possible hands because only the suits matter, but we do have to be careful about how we count. We begin with a full deck of cards (52 distinct cards). Let’s suppose we want to count hands of size 2. There are $52\cdot 51 = 2652$ possible hands. But since numbers don’t matter, we can remove the number and just look at suits. There are then 16 possible hands:
  \[
  \begin{array}{cccc}
  ♠♠ & ♠♣ & ♠\color{red}{♥} & ♠\color{red}{♦} \\
  ♣♠ & ♣♣ & ♣\color{red}{♥} & ♣\color{red}{♦} \\
  \color{red}{♥}♠ & \color{red}{♥}♣ & \color{red}{♥}\color{red}{♥} & \color{red}{♥}\color{red}{♦} \\
  \color{red}{♦}♠ & \color{red}{♦}♣ & \color{red}{♦}\color{red}{♥} & \color{red}{♦}\color{red}{♦}
  \end{array}
  \]suppose for example that the hands with different suits but same color are not sortable. There are four such hands: $\{ ♠♣, ♣♠, \color{red}{♥}\color{red}{♦}, \color{red}{♦}\color{red}{♥} \}$. Then we might conclude that $\tfrac{4}{16} = 0.25$ of hands are not sortable. But this would be wrong! (thanks to Guy Moore for pointing this out). The reason is that these 16 hands don’t all occur with equal probability. There are $13\cdot 13 = 169$ ways of picking two cards of different suits, but only $13\cdot 12 = 156$ ways of picking two cards of the same suit! So each type of card should be weighted by its likelihood of occurrence. This means the probability of picking an unsortable hand should really be:
  \[
  \frac{4\cdot 169}{4\cdot 156 + 12\cdot 169} = \frac{13}{51} \approx 0.2549
  \]So we can collapse the large number of possible hands to this more manageable size as long as we compensate by appropriately weighting the different items. In combinatorics, this collapsed group of cards (where we care about the order and the suit, but not the number of the card) is an example of a multiset permutation.

  Note: If we don’t weigh the hands according to likelihood (i.e. assume all hands are equally likely), this is equivalent to assuming the deck has infinitely many cards (but the same number of cards in each suit).

• Adjacent cards of the same suit can be collapsed to a single card. This is because there is never any benefit to moving a block of cards if it splits an existing contiguous block. So for example:
  \[
  \{♠,♠,\color{red}{♥},\color{red}{♥},\color{red}{♦}\} \implies \{♠,\color{red}{♥},\color{red}{♦}\}.
  \]This greatly reduces the computations because if two different hands collapse to the same reduced hand, we only need to do the work for one of them! In computer programming, this technique of storing the values of computations so that you don’t end up computing the same thing many times is called memoization.

• If a hand consists of $N$ cards (after we collapse adjacent suit repetitions as described above), then there are $\binom{N+1}{3}$ possible moves we can make. This is because every move is characterized by three locations. I’ll illustrate this with an example. Say our hand looks like this: $\{♠,\color{red}{♥},\color{red}{♦},♠,\color{red}{♥},♣\}$ and we want to sort it by moving cards 4 and 5 and inserting them between cards 1 and 2. In other words, we want to perform:
  \[
  \{♠,\color{red}{♥},\color{red}{♦},(♠,\color{red}{♥}),♣\} \implies \{♠,(♠,\color{red}{♥}),\color{red}{♥},\color{red}{♦},♣\}
  \implies \{♠,\color{red}{♥},\color{red}{♦},♣\}
  \]where we did one final collapse at the end. This transformation can be represented by inserting three “bars” between cards as follows. Then the swap simply consists of exchanging the cards between the two pairs of bars! Here is the diagram:
  \[
  \{\,♠\,\,|\underbrace{\color{red}{♥}\,\,\color{red}{♦}}_\text{swap this}|\underbrace{♠\,\,\color{red}{♥}}_\text{with this}|\,\,♣\,\}
  \implies \{♠, ♠, \color{red}{♥},\color{red}{♥},\color{red}{♦},♣\}
  \]Each triplet of bars corresponds to a possible swap, and we can insert bars in $N+1$ possible spots (in between each card and on either end).

• If the hand has 8 or more cards in it after we perform the collapse, then it’s impossible to sort it in one move. This is because our final hand can have at most 4 groups of cards in it, and a single move can cause at most 3 collapses. With 8 cards, we can get down to 5 but not 4. Here is an example of a 7-card hand that can be sorted in one move:
  \[
  \{\,♠\,|\,\color{red}{♥}\,♣\,|\,♠\,\color{red}{♥}\,|\,♣\,\color{red}{♦}\,\}
  \implies \{\,♠\,♠\,\color{red}{♥}\,\color{red}{♥}\,♣\,♣\,\color{red}{♦}\,\}
  \implies \{\,♠\,\color{red}{♥}\,♣\,\color{red}{♦}\,\}
  \]

Numerical results

There was a bit of confusion as to how to interpret the meaning of the requirement “the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent”. One way to interpret this statement is that we only require cards of a different suit but same color to be separated if it’s actually possible to separate them. For example, the two-card hand $\{\color{red}{♥}\,\color{red}{♦}\}$ counts as being sorted because there are no spades or clubs that can be placed between the heart and the diamond. In this scenario, here are the results:

Note that hands of up to size $N=4$ are always sortable in one move. The exact solution for the case $N=6$ using this interpretation is $\tfrac{51083}{83895} \approx 60.8892\%$. Another way to interpret the requirement is that cards of a different suit but same color can never be adjacent. This means that hands like $\{\color{red}{♥}\,\color{red}{♦}\}$ are never sortable no matter what you do. In this case, we get the result:

It’s interesting to note that the probability of a “sortable” hand in this interpretation actually reaches a maximum when $N=4$ and then decreases afterwards. The exact solution for the case $N=6$ using this interpretation is $\tfrac{1735996}{2936325} \approx 59.1214\%$.

I wrote my code in Julia, and you can view my notebook here. The computation gets slower in an exponential fashion as we increase $N$. The cases $N \leq 8$ take on the order of seconds, but computation time quadruples every time $N$ increases by 1. The last case, $N=13$, took about 40 minutes! While there is a significant amount of computation to do, there is also significant computational overhead due to using exact arithmetic instead of making approximations. For this, I used Julia’s BigInt datatype. So the solutions I obtained were exact. For example, the probability of a sortable hand for $N=13$ (using the first interpretation) turns out to be:
\[
\tfrac{10954472929065768960}{3954242643911239680000} = \tfrac{30785713171}{11112737293000} \approx 0.27703\%
\]Using approximations the whole way leads to a computation time of less than 10 minutes for the most complicated case.