Algorithm to find an optimum number of rummy-style sets?

Question

I'm developing a card game that uses rummy-style sets of three cards. From a random selection of cards, I need the algorithm to pick out which cards would get me the highest number of sets.

By "rummy-style sets of three" I mean:

• All three cards have the same value, like three Jacks. OR
• All three cards are of the same suit and sequential in order, like a 7, 8, 9 all of diamonds.

For example, given the cards: 6D, 7D, 7C, 7H, 8D, 8C, 9C, 10H
I could form the set: {7D, 7C, 7H}, but that would be the only set I would get out of it, and it would not be optimum.
The optimum sets in this case are: { {6D, 7D, 8D}, {7C, 8C, 9C} }

I have tried brute force (permute through all the given cards, see what matches in order in that permutation), but that proved too slow. The problem feels like it has similarities to other solved problems, and that's why I ask here.

Answer 1

if you have N cards (N = 8), you can enumerate through all the distinct triples in the set in time N * (N - 1) * (N - 2) (with N = 8 you get 336). This is pretty fast. Check which ones of the triples are "rummy-style" sets, and store them in a table as integer triples (the integer denote the sequence numbers of the cards).

That's the first step. The second step is now to do combinatorial optimization and calculate the optimal choice. The simple way to do this is to use backtracking search. You run an index ('i') over the set of triples you have found. First you try to include the 'i'th triple in the solution, and then continue from index i+1 recursively; then you backtrack and decide that the 'i'th triple is not in the solution, and continue from i+1 recursively. There are many optimizations to this, but for the small sets it's going to work pretty fine.

Here how it works with your example:

Cards: 6D, 7D, 7C, 7H, 8D, 8C, 9C, 10H

Let's enumerate all the possible triples:

Cards        Index triple
6D 7D 8D     <0, 1, 4>
7D 7C 7H     <1, 2, 3>
7C 8C 9C     <2, 5, 6>

The full backtracking search goes like this:

Decide on <0, 1, 4>:
  <0, 1, 4> INCLUDED:
     <1, 2, 3> CLASHES with <0, 1, 4>
     Decide on <2, 5, 6>:
       <2, 5, 6> INCLUDED:
          Solution with 2 sets (* BEST SOLUTION)
       <2, 5, 6> EXCLUDED:
          Solution with 1 sets
  <0, 1, 4> EXCLUDED:
     Decide on <1, 2, 3>:
        <1, 2, 3> INCLUDED:
           <2, 5, 6> CLASHES with <1, 2, 3>
           Solution with 1 sets
        <1, 2, 3> EXCLUDED:
           Decide on <2, 5, 6>:
             <2, 5, 6> INCLUDED:
                Solution with 1 set
             <2, 5, 6> EXCLUDED:
                Solution with 0 sets

Then you pick the solution with most sets (marked with asterisk).

This is pretty simple to implement. Try it!