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

My intuitive approach would be to start by discovering all the possible sets, by examining each card and searching for what can make a set with that card (i.e. consecutive things and same-value-things.) Once you've got all the possible sets, which should be a pretty quick operation unless you have a really large amount of cards, then you can make a map of which sets preclude the inclusion of other sets (they use the same cards.) At that point, even permuting all the legal combinations of sets (for each of the sets that i don't have; try adding it if i can legally use it in my current set of sets; repeat) should be fast enough to serve.

Answer 2

Hi,

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!

Answer 3

To find all possible valid triples, you could do 2 steps:

1. sort cards first ascending by number, then by suit, as you did
   in your example and look what triples you can get
2. now sort a second time, but first by suit and then by number 
   and look what triples you can get

In step 1) you can just look sequencially for 3 same numbers => O(n)
In step 2) the same, but now looking for 3 sequential numbers of the same suit. => O(n)

Merging the two results gives you all possible triples. If I'm not wrong, at this point you reached the NP-hard problem of maximum set packing, as you want to get the maximum subset of non-overlapping triples. As the number of cards is limited and not so high you could use for example the backtracking algorithm that antti.huima mentioned for solving this problem.