Generate all possible teams

[andrea crotti]

Hi everyone,

I was trying for fun to solve the following problem:

given a list of football players with some defined skills, find out which
team selection would be balanced.

For example given just 4 players A, B, C, D there would be the following
team selections:

- (A, B) vs (C, D)
- (A, C) vs (B, D)
- (A, D) vs (B, C)

So it's a combinatorial problem however both inside teams and inside the
selection the order does not count, so the number of possible teams
is a lot smaller than the actual all possible permutations.

I came up with a brute force solution here:

https://github.com/AndreaCrotti/football/blob/master/src/cljc/football/engine.cljc#L75

which however explodes already for 12 players because:

- it does all the possible permutations of teams (12! in that case)
- partition accordingly (using sets to remove duplicates) and evaluate
every single one of them

Any idea how to make this faster?
Other advices on the code are welcome as well..

Thanks

[Franklin M. Siler]

On Oct 5, 2015, at 0545, andrea crotti <andrea....@gmail.com> wrote:

> Any idea how to make this faster?
> Other advices on the code are welcome as well..

Why not generate the the possible left-hand teams and then cartesian product with the leftover players? E.g., if you want to match 2 on 2 and have players A B C D E:

(A,B) cartesian product with (combinations #{C D E})
(B,C) cartesian product with (combinations #{A D E})
and so on with
(C,D)
(D,E)

I think this will generate each possible match exactly twice- mirror images of each other, but proof is left as an exercise for the reader.

I would imagine there is a better algorithm for this than mine.

Cheers,

Frank Siler
Siler Industrial Analytics
314.799.9405

[Mark Engelberg]

Are there an even number of players?

Are all players assigned to teams?

Are the two teams necessarily of equal sizes?

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Alan Forrester]

I find your code unclear. I can’t tell what problem you’re trying to solve by reading the code or the comments. Do you have a specification of what problem you’re trying to solve? If not, you should write one before you do anything else.

Having said that, there is one way I can see that you might make the code slightly less bad. You define a field for your players called “:position” and then never use it. I know almost nothing about football, but I should think you might want the team to have at least one player in each position. So I might do something like (group-by :position players)

https://clojuredocs.org/clojure.core/group-by.

Then I might generate teams by picking one player in each position or something like that. This would reduce the number of combinations by some unknown amount. More generally, if you have too many combinations, introduce constraints in how you generate them.

Alan

[Mark Engelberg]

Sample input data would also be useful, including some examples that are too large for you to currently solve with your existing approach.

[andrea crotti]

Yes so well for example the rankings can be defined in this way

[{:name "P1"
:skills {:control 3
:speed 3
:tackle 4
:dribbling 10
:shoot 4}
:position :attack}

{:name "P2"
:skills {:control 3
:speed 3
:tackle 4
:dribbling 10
:shoot 4}
:position :attack}]

and the list of players
["P1"
"P2"]


Assuming they are in two different files then calling
lein run -r sample_rankings.edn -l sample_players.edn

would produce the desired result.

Well the input gets too big already for 12 players (I didn't wait it
to finish but 12! is 39916800), while it still works in around 2
minutes for 2 players.

The real alternative would be to do some dynamic programming but I was
just hacking something together now and I'm sure even the brute force
can still work quite well in theory..

[andrea crotti]

1. it could be odd in case we don't manage, the first solution I did
was just a greedy algorithm, but that only worked with even number of
players
2. yes well now I pass the rankings and the list of players
separately, but yeah every player will be part of a team
3. this looks the same as 1), and sometimes there can be 5 vs 6 for example

[andrea crotti]

Yes this could actually work thanks, I only need to iterate over all
the possible permutations of the first partition and combine it, still
certainly a lot less stuff to compute.

[Mark Engelberg]

You're not using the combinatorics library as efficiently as you could be.  Here's the best strategy for generating all the team combinations with the same number of players:

Case 1: Even number of players.

Let's call the first player "A".  "A" is going to be assigned to a team.  To avoid duplication, we want to find all the team combinations that will include player "A".  Then we can figure out the opposing team in each case by simply subtracting the team with player "A" from the total set of players.  Compare their skill sets as you did in your code.

So to get the teams with player A, you simply add in A to all the (n/2)-1 size subsets of (rest players).

Case 2: Odd number of players.

Add player A to all the (n-1)/2 and (n-1)/2-1 subsets of (rest players).

This should be substantially more efficient than your strategy involving permutations.

Furthermore, you are essentially reducing the players down to a single skill value.  Your code code be even more efficient if you just work with the final skill values directly, because combinatorics uses a more efficient strategy when it sees duplicate values; if two players have the same skill value, there's no real reason to view them as distinct.  Get two balanced sets of skill values and then match them back up with the players at the end.

Beyond this brute force strategy, it would be interesting to model this problem using the Clojure library "loco", which can optimize using a branch-and-bound strategy which is more efficient than trying every possible combination.  (I can provide an example of that if you are interested).  Loco can also take a timeout at which it will return the best thing it has found so far.

Another route is to use Clojure to generate a model to be passed into a mixed-integer optimization solver.

Once you are dealing with so many players that it is impractical to find the optimal solution, you need to look at heuristics. Often, a very simple strategy works really well, for example, sort the team into two equal groups and randomly make swaps of players between the two teams if it balances things out.  When you can't improve things further, restart from another random division.  Do this many times and take the best match-up you've found.  It will likely be close to optimal.  Beyond that, heuristics like tabu search, simulated annealing, genetic algorithms, etc. help you avoid getting stuck at a local optimum and get closer to the true optimum.

[Fluid Dynamics]

On Monday, October 5, 2015 at 2:33:50 PM UTC-4, puzzler wrote:

You're not using the combinatorics library as efficiently as you could be.  Here's the best strategy for generating all the team combinations with the same number of players:

Is a combinatorics library even needed for this?

(-> (for [a teams
          b teams
          :when (= (count a) (count b))]
       #{a b})
  (hash-set))

Should produce all distinct pairs with equal player counts, given that "teams" is bound to a collection of teams, each of which is a collection of player objects, and "seq" works on the former collection and "count" on the latter ones. If each team is something more complex (e.g. a map with a :players key) things get only slightly more complicated (e.g. changing (count a) to (count (:players a))).

[andrea crotti]

2015-10-05 19:33 GMT+01:00 Mark Engelberg <mark.en...@gmail.com>:
> You're not using the combinatorics library as efficiently as you could be.
> Here's the best strategy for generating all the team combinations with the
> same number of players:
>
> Case 1: Even number of players.
> Let's call the first player "A". "A" is going to be assigned to a team. To
> avoid duplication, we want to find all the team combinations that will
> include player "A". Then we can figure out the opposing team in each case
> by simply subtracting the team with player "A" from the total set of
> players. Compare their skill sets as you did in your code.

Yes I came up with the same idea in the end, this is the code that does that.

(defn list-teams-combo [players]
"List all the possible team combinations"
(let [players-count (count players)
size (/ (combo/count-combinations players 2) 2)
team-size (/ (count players) 2)]

(for [team1 (take size (combo/combinations players team-size))]
(list team1 (into () (clojure.set/difference (set players) team1))))))

For how combinations work also the nice thing is that I can just go
until the middle so this seems to work well :)

>
> So to get the teams with player A, you simply add in A to all the (n/2)-1
> size subsets of (rest players).
>
> Case 2: Odd number of players.
> Add player A to all the (n-1)/2 and (n-1)/2-1 subsets of (rest players).
>
> This should be substantially more efficient than your strategy involving
> permutations.
>
> Furthermore, you are essentially reducing the players down to a single skill
> value. Your code code be even more efficient if you just work with the
> final skill values directly, because combinatorics uses a more efficient
> strategy when it sees duplicate values; if two players have the same skill
> value, there's no real reason to view them as distinct. Get two balanced
> sets of skill values and then match them back up with the players at the
> end.

Yeah well about that I realized that during the possible teams generation
I don't need to carry around all the values, all I care about is the
name of the player.
The final skill value can be computed later anyway once I have all possible
teams selections..

>
>
> Beyond this brute force strategy, it would be interesting to model this
> problem using the Clojure library "loco", which can optimize using a
> branch-and-bound strategy which is more efficient than trying every possible
> combination. (I can provide an example of that if you are interested).
> Loco can also take a timeout at which it will return the best thing it has
> found so far.

Yes that would be interesting sure I'll give a look.

>
> Another route is to use Clojure to generate a model to be passed into a
> mixed-integer optimization solver.
>
>
> Once you are dealing with so many players that it is impractical to find the
> optimal solution, you need to look at heuristics. Often, a very simple
> strategy works really well, for example, sort the team into two equal groups
> and randomly make swaps of players between the two teams if it balances
> things out. When you can't improve things further, restart from another
> random division. Do this many times and take the best match-up you've
> found. It will likely be close to optimal. Beyond that, heuristics like
> tabu search, simulated annealing, genetic algorithms, etc. help you avoid
> getting stuck at a local optimum and get closer to the true optimum.
>
>

Yeah that's a good idea, the first implementation was just a greedy selection
(get the next best player available) and it still works reasonably
well, specially
if the players are more or less on a similar level.
It would be interesting also to train the settings I could add with
some human input,
there are so many adjustements I could do to how the scoring works..

Thanks a lot anyway

[Mark Engelberg]

On Mon, Oct 5, 2015 at 1:08 PM, andrea crotti <andrea....@gmail.com> wrote:

Yes I came up with the same idea in the end, this is the code that does that.

(defn list-teams-combo [players]
  "List all the possible team combinations"
  (let [players-count (count players)
        size (/ (combo/count-combinations players 2) 2)
        team-size (/ (count players) 2)]

    (for [team1 (take size (combo/combinations players team-size))]
      (list team1 (into () (clojure.set/difference (set players) team1))))))

This line is wrong:

size (/ (combo/count-combinations players 2) 2)

You mean (for even number of players):
size (/ (combo/count-combinations players (/ players-count 2)) 2)

 

[Alan Moore]

Not sure it would be a lot more efficient but you could try using logic/relational programming with core.match, a datalog library or even a rule engine such as Clara. With the later you can use heuristics to trim the search space as another poster suggested.

Good luck.

Alan

[Gerrit Jansen van Vuuren]

Have a look at http://www.afronski.pl/sicp-in-clojure/2015/10/05/sicp-in-clojure-chapter-4.html  scroll to "Ambiguous operator", 

this implements searching for combinations in a search space based on the conditions you give it using backtracking,

also as already mentioned you could directly go for logic programming which is also explained in the above post.