# Re: Algorithm for evenly distributing objects

*From*: "Rilo" <mriley@xxxxxxxxxxxxxxxxxxxxxx>*Date*: 31 Aug 2006 20:02:59 -0700

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 :-)

.

**References**:**Algorithm for evenly distributing objects***From:*Rilo

**Re: Algorithm for evenly distributing objects***From:*goose

- Prev by Date:
**Re: modulo** - Next by Date:
**Re: Algorithm for evenly distributing objects** - Previous by thread:
**Re: Algorithm for evenly distributing objects** - Next by thread:
**Re: How to compute triangle base/altitude intersection** - Index(es):