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.

-- 
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.

Reply via email to