snippetMinor
Algorithm to find sequence of minimum moves to sort 13 card hand
Viewed 0 times
handmovesminimumcardsequencealgorithmfindsort
Problem
Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand.
A sorted bridge hand is arranged by suit, with alternating colors of suit (if possible), and the cards are sorted by decreasing rank within each suit. For example
The goal is to sort the 13 randomly dealt cards using the least number of the following human-like moves:
What is an efficient algorithm to find the sequence of the minimum number of such moves to sort the hand?
A sorted bridge hand is arranged by suit, with alternating colors of suit (if possible), and the cards are sorted by decreasing rank within each suit. For example
- ♣QJ3♥K4♠AQ974♦K76 is a sorted hand
- ♥K4♣QJ3♠AQ974♦K76 is not a sorted hand because the two black suits are touching
- ♣QJ♥K4♠AQ974♦K76♣3 is not a sorted hand because the clubs are not together
- ♣3JQ♥K4♠AQ974♦K76 is not a sorted and because the clubs are not sorted in decreasing rank.
The goal is to sort the 13 randomly dealt cards using the least number of the following human-like moves:
- A card can be temporarily removed from the hand and inserted back somewhere else. For example the ♣3 in ♣QJ♥K4♠AQ974♦K76♣3 can be inserted after the second card to sort the hand.
- Any number of consecutive cards can similarly be removed from the hand and inserted back somewhere else. For example the ♣QJ3 in ♥K4♣QJ3♠AQ974♦K76 can be moved to the front. This is considered one move.
What is an efficient algorithm to find the sequence of the minimum number of such moves to sort the hand?
Solution
This problem is harder than you might think. Your operation of removing a block of adjacent cards and re-inserting the block somewhere else is known as a transposition. Sorting by transpositions has been studied in the context of bioinformatics and is known to be hard. Of course, if you limit the length to 13 cards, then efficiency becomes much less of a concern--even an exponential algorithm is likely to be fast enough.
I recommend breaking the problem into two related parts. The first, lower level, is to write an algorithm for sorting by transposition on an array of integers, more specifically, on an array that is a permutation of the numbers 1..N. This may be inefficient, but for small N, should be fast enough.
The second, higher level part, is to consider the possible arrangements of suits (clubs-hearts-spades-diamonds, ...). There are at most 8 legal arrangements of suits, and fewer if one or more suits are missing. For each arrangement of suits, it is easy to calculate, for each of the 13 cards, what position it should end up at, giving you an array of the numbers 1..13. Then you can call the first part above as a subroutine.
I recommend breaking the problem into two related parts. The first, lower level, is to write an algorithm for sorting by transposition on an array of integers, more specifically, on an array that is a permutation of the numbers 1..N. This may be inefficient, but for small N, should be fast enough.
The second, higher level part, is to consider the possible arrangements of suits (clubs-hearts-spades-diamonds, ...). There are at most 8 legal arrangements of suits, and fewer if one or more suits are missing. For each arrangement of suits, it is easy to calculate, for each of the 13 cards, what position it should end up at, giving you an array of the numbers 1..13. Then you can call the first part above as a subroutine.
Context
StackExchange Computer Science Q#43668, answer score: 3
Revisions (0)
No revisions yet.