Total Posts:4|Showing Posts:1-4
Jump to topic:

Ideas Regarding My Program

Cobalt
Posts: 991
Add as Friend
Challenge to a Debate
Send a Message
11/14/2015 7:51:03 PM
Posted: 1 year ago
So I'm currently writing a program, GUI included, totally in Python for a local golf course. Basically, you input the players, their specific handicaps and how many people you'd like per team.

I've already figured out an acceptable way of converting handicaps to actual likely performance and figuring out a given teams likelihood of success. I've additionally already built in a handler for when num_players % team_size != 0. The goal is to determine precisely which team arrangement(s) have the least variation in their likelihood of success.

This is where I'm running into difficulties. Currently, I take the list of players, then generate every possible ordering of the players using itertools. For example, if there are players 1, 2, 3, 4 then the possibilities are:

1234
1243
1324
1342
. . .
4321

I then break this down into teams, like so:

[1,2] [3,4]
[1,2] [4,3]
. . .
[4, 3] [2, 1]

Then I calculate the teams comparative skill and return the "best team combination".

Itertools can generate these possibilities very quickly when the number of players is small, however when you have 20+ players the exponential growth in the calculation time becomes so large that it would take hours/days/year to complete. This type of generation obviously returns duplicate teams (since [1,2] [3,4] is the same as [4,3] [2,1], but I can't seem to determine an algorithm that can avoid computing repeats to drastically reduce computation time.

Currently, I have a function that takes the list of player's handicaps, the desired team size and a "quality" integer. The latter parameter basically just loops that many times, each time randomizing the list of players, breaking off teams and then computing comparative advantage. With quality = 10,000 I see pretty consistent and low variance, but it bugs me that this method does not guarantee the best possible team combination.

Does anyone know of a better way to do this or any built-in or otherwise algorithm that tackles this problem? I'd really like to insure that the function returns the absolute best possible team combination for any number of players (less than 1,000 or so) in a reasonable amount of time (<5 seconds).

I read that Python's itertools is really awful at this particular task, for some reason, and that other languages perform better -- but time constraints don't afford me the opportunity to familiarize myself with another language to the degree I am familiar with Python.

Any help is greatly appreciated.
Dirty.Harry
Posts: 1,585
Add as Friend
Challenge to a Debate
Send a Message
12/4/2015 4:54:08 PM
Posted: 1 year ago
At 11/14/2015 7:51:03 PM, Cobalt wrote:
So I'm currently writing a program, GUI included, totally in Python for a local golf course. Basically, you input the players, their specific handicaps and how many people you'd like per team.

I've already figured out an acceptable way of converting handicaps to actual likely performance and figuring out a given teams likelihood of success. I've additionally already built in a handler for when num_players % team_size != 0. The goal is to determine precisely which team arrangement(s) have the least variation in their likelihood of success.

This is where I'm running into difficulties. Currently, I take the list of players, then generate every possible ordering of the players using itertools. For example, if there are players 1, 2, 3, 4 then the possibilities are:

1234
1243
1324
1342
. . .
4321

I then break this down into teams, like so:

[1,2] [3,4]
[1,2] [4,3]
. . .
[4, 3] [2, 1]

Then I calculate the teams comparative skill and return the "best team combination".

Itertools can generate these possibilities very quickly when the number of players is small, however when you have 20+ players the exponential growth in the calculation time becomes so large that it would take hours/days/year to complete. This type of generation obviously returns duplicate teams (since [1,2] [3,4] is the same as [4,3] [2,1], but I can't seem to determine an algorithm that can avoid computing repeats to drastically reduce computation time.

Currently, I have a function that takes the list of player's handicaps, the desired team size and a "quality" integer. The latter parameter basically just loops that many times, each time randomizing the list of players, breaking off teams and then computing comparative advantage. With quality = 10,000 I see pretty consistent and low variance, but it bugs me that this method does not guarantee the best possible team combination.

Does anyone know of a better way to do this or any built-in or otherwise algorithm that tackles this problem? I'd really like to insure that the function returns the absolute best possible team combination for any number of players (less than 1,000 or so) in a reasonable amount of time (<5 seconds).

I read that Python's itertools is really awful at this particular task, for some reason, and that other languages perform better -- but time constraints don't afford me the opportunity to familiarize myself with another language to the degree I am familiar with Python.

Any help is greatly appreciated.

This sounds like (I've only glossed over what your wrote though) a problem well suited to a functional programming language like F# or Scala.

My first reaction here though (as an experienced programmer) is how have others solved this before? surely working with this data in the domain of golf isn't something new?

Harry.
Dirty.Harry
Posts: 1,585
Add as Friend
Challenge to a Debate
Send a Message
12/4/2015 4:57:31 PM
Posted: 1 year ago
A tip here is to solve the problem for a small number of players, say 3 then 4.

Then scrutinize your solution to that problem to see if it can be minimized/simplified.

Also although I enjoy discussing algorithms etc it may be more practical for you to visit StackExchange or CodeProject etc to seek input.

Harry.
Deb-8-A-Bull
Posts: 2,181
Add as Friend
Challenge to a Debate
Send a Message
12/24/2015 2:44:42 PM
Posted: 11 months ago
At 12/4/2015 4:57:31 PM, Dirty.Harry wrote:
A tip here is to solve the problem for a small number of players, say 3 then 4.

Then scrutinize your solution to that problem to see if it can be minimized/simplified.

Also although I enjoy discussing algorithms etc it may be more practical for you to visit StackExchange or CodeProject etc to seek input.

Harry.

This is why I don't eat sun dried tomatoes.