# How to extract a subset of trading cards from a larger set based on arbitrary rules

I have a set of approximately 20,000 different football (soccer) trading cards (for those interested, this question is based on FIFA Ultimate Team). Each represents a football player and the card has an ability rating between 1 and 99. The higher the rating, the better the player's ability.

A player of this card game purchases 11 cards to form a team to use against the teams of other players. In this game, each team has a "chemistry" rating, between 1 and 100, which is dynamically calculated by the combinations of players in the team. Players are represented by their nationality, club and the league in which their clubs play, so players who play together that share leagues, nationalities or clubs have good chemistry levels, while those who do not, have bad chemistry levels. There are some other rules, but for the purpose of this question we can ignore them for now.

I want to figure out how to generate a team of 11 cards based on arbitrary rules. So for example, I want to be able to use some sort of algorithm or function to say "given the full set of players available, give me a squad with a minimum overall rating of 80 with a minimum 95 chemistry rating." Another example could be "given the full set of players available, give me the highest possible rated squad with a 100 chemistry rating, using only Italian players." The algorithm would then iterate through the entire set and return a squad of 11 based on the stated rules.

From the research I've done, I believe that this is a combinatorial optimisation problem, but I'm an average software engineer and not a mathematician so I'm unsure on how to proceed with this. Ideally, I'd like to take the answer to this and turn it into a library written in PHP or perhaps Python.

• I have not mastered the details of your problem, but often such combinatorial problems are difficult (non-polynomial complexity) to solve exactly, and one then may be motivated to pursue approximate solutions. In your case the "stated rules" and "arbitrary rules" don't give Readers much indication of whether exact optimums or approximate optimums are most suitable. – hardmath Apr 19 '18 at 18:38
• @hardmath Many thanks for your comment and apologies that my question doesn’t give enough detail. I’m unsure what’s suitable myself, as this is not my area of expertise, but any sort of nudge in the right direction is very much appreciated. Thanks again. – Jamie Hollern Apr 19 '18 at 18:46
• You can't "iterate through the entire set" if by that you mean construct all possible teams. There are $5116579369477560619072992589136011820000$ possible $11$-man teams from $20000$ players. – saulspatz Apr 19 '18 at 18:55
• @saulspatz Indeed! Sorry about my garbage terminology. I could manually figure this out, in code, by doing exactly what you've stated, but obviously that would be massively slow and inefficient. So I guess some sort of algorithm would be necessary to avoid that - I just don't know what I'm looking for. – Jamie Hollern Apr 19 '18 at 19:14
• It seems to me that the first thing to do is to eliminate most of the players from consideration. Why would you consider any but the highest-rated players? Then you might try grouping the remaining players into affinity groups with high "chemistry" using k-means or some other clustering algorithm. Perhaps there's more to the choosing than I understand -- I don't know the first thing about soccer. – saulspatz Apr 21 '18 at 15:01