CODEWITHSUNDEEP
algorithmrandom
mawimawi
mawimawi

Reputation: 4333

How to create an even distribution over multiple sets?

This is for a hobby project and will be implemented with Python, but this is not really important. I'm mostly looking for a good algorithm.

I want to host a racing event with 2 to 30 drivers (num_drivers). The event has 2 to about 12 races (num_races), and I want each driver to have a fair chance according to their position at the start using somewhat random positioning. The problem is, which starting positions do I assign to each driver for each race?

An example: for an event with num_races=3 and num_drivers=4 (named "A" to "D") a pretty good setup would be

Race 1: A B C D
Race 2: C D B A
Race 3: D B A C

The pole position would have a value of 1, the second position 2, and so on. So this setup gives quite equal values to each driver:

A: 1+4+3 = 8
B: 2+3+2 = 7
C: 3+1+4 = 8
D: 4+2+1 = 7

In the end the sum of positions of each driver should ideally be the same as for every other driver. What would be a good generic algorithm (in pseudo code) for my problem when the number of drivers and number of races can vary? Is there even already an algorithm somewhere to look at?

Upvotes: 2

Views: 123

Answers (2)

mawimawi
mawimawi

Reputation: 4333

I found a nicely working PHP script on github that solves the problem for me. So if anyone's interested in the answer to my problem: https://github.com/FriendlyBaron/GridCreator

Upvotes: 0

3Dave
3Dave

Reputation: 29051

I'd start with:

Race 1: A B C D
Race 2: A B C D
Race 3: A B C D

And rotate each row by the race number,

Race 1: A B C D 
Race 2: D A B C
Race 3: C D A B

Giving:

A = 1 + 2 + 3  = 6
B = 2  + 3 + 4 = 8
C = 3 + 4 + 1  = 8
D = 4 + 1 + 2  = 7

Which is a decent distribution, and about as good as you're going to get (I think!) with this size of a pool.

Random will work if you have a LOT of drivers.

You could always do this, find your lows and highs, and correct closed-loop. So, in the example above, I'd note that A is << B and C, so I could swap the high C(4) with the next high A(3) and wind up with 7,8,7,7.

Trivial for this size of a set, but probably not so much with larger grids.

If you had 4 races, you would get DC (score of 10 for every driver), but I doubt you want to have 64 races for 64 drivers (for instance).

Another approach would be to determine the score you want for each driver, then work backwards to generate the grid. Use a weighted queue - highest priority given to the driver with the lowest score - and, when populating the grid, just grab the driver with the lowest score to put in the current highest position. It's a little like the bin packing problem, but should work reasonably well.

Upvotes: 1

Related Questions