Re: Algorithm for evenly distributing objects



Thanks, Goose. I had tried a similar technique, but had problems. By
starting with the property that has the most variance, and reversing
the sort order each time, maybe I can get it working now.

Mike

goose wrote:
Rilo wrote:
Given a group of objects, each with a specified number of properties,
is there an algorithm for distributing the objects into a specified
number of groups, such that the properties are divided evenly (as close
as possible) among the groups?

Example:
Given: Six circles that have two properties: color (red or white) and
diameter (1, 2 or 3).
Circle1: white, 1
Circle2: white, 2
Circle3: red, 2
Circle4: red, 2
Circle5: red, 2
Circle6: red, 1
Circle7: red, 3
Circle8: red, 3
Problem: Divide the six circles into two groups.
Solution:
Group1: Circle1, Circle3, Circle4, Circle7
Group2: Circle2, Circle5, Circle6, Circle8

Each resulting group gets: one 'white', three 'red', one '1', two '2s'
and one '3'.
This is a simplified example, and there is more than one solution, but
hopefully this demonstrates the problem.

Thanks for any suggestions of algorithms I might be able to research.


Sort them on their properties with the first key being
the property with the largest variance, the second key being
the property with the second largest variance[1], etc. Each
time you exhaust all elements with a certain key-property,
reverse (ascending to descending of vice versa) the sort for
the rest of the elements[2].

With just two keys it simply means that you sort on
the primary key (say ... radius) and reverse the sort
for each set of primary keys (colour). With more than
two keys (say, colour, radius and opacity) you reverse
sorting on SK when out of radius, then reverse the
sorting on the third key when out of colour. If
the number (amount) of any key cannot be divided by the
number of groups without remainder then a solution
cannot be found (e.g. having 3 "red" and 5 groups
will never result in a solution).

Then just round-robin them into each group (will work on
more than two groups as well).
Using your example:
(Primary key (PK) = radius, second key (SK) = color)
(We start sort on descending on SK)
Circle1: white, 1 -> G1
Circle6: red, 1 -> G2 (out of PK, reverse to ascending on SK)
Circle3: red, 2 -> G1
Circle4: red, 2 -> G2
Circle5: red, 2 -> G1
Circle2: white, 2 -> G2 (out of PK, reverse to descending on SK)
Circle7: red, 3 -> G1
Circle8: red, 3 -> G2


[1] Or smallest variance, then second smallest, etc.
[2] The reversing of the sort is needed so that the
first key does not bias the rest of the keys
(I think!:).

WARNING: I don't have the proof handy that this algorithm
is infallible, but I believe it to be. Proving it
works for M groups with N keys with M | M > 2 and
N | N/M==whole number is left as an exercise to the
reader.

goose,
have fun now kids :-)

.



Relevant Pages