2015-10-05 19:33 GMT+01:00 Mark Engelberg <mark.engelb...@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
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
