Algorithm to partition a list into groups

Question

I have a list of names.

I want to partition this list into groups of a specified size. All groups should be equal to or less than the specified size, with an equal as possible group size across the groups, and as close to the specified size as possible.

What algorithm (Java-esque pseudo code if possible please!) determines the most appropriate group sizes?

For example:

List contains 13 names - max team size 3. Output (group sizes): 3, 3, 3, 2, 2

List contains 13 names - max team size 4. Output: 4, 3, 3, 3

List contains 31 names - max team size 5. Output: 5, 5, 5, 4, 4, 4, 4

List contains 31 names - max team size 6. Output: 6, 5, 5, 5, 5, 5

List contains 31 names - max team size 10. Output: 8, 8, 8, 7

1,1,1,1,1,1,1,1,1,1,1,1,1 also has max 3 items in each group and the group sizes are more equal than in your example. — Robert
– Robert, Commented Jan 12, 2012 at 14:39
The expected output is not clear. For example, what's the output for: List contains 31 names - max team size 10 — Óscar López
– Óscar López, Commented Jan 12, 2012 at 14:50

Grooveek · Accepted Answer · 2012-01-13 08:30:36Z

4

It's pretty straightforward. You calculate the result of N div M and add 1 to have the correct number of arrays (N is the list length and M the max team size), then you iterate on all arrays to add an item until you run out of items

example : 43 names, max team number 4 => 43 mod 4 + 1 = 11, remains 3. so 11 arrays (10 with 4 and 1 with 3)

edited Jan 13, 2012 at 8:30

answered Jan 12, 2012 at 14:38

Grooveek

10.1k1 gold badge30 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sergey Kalinichenko Over a year ago

You probably meant div, not mod, because 43 mod 4 is 3, not 10 (mod means remainder, not integer division). Also +1 would not work if M divides N without a remainder. You need to do (N+M-1) div M to get the result you are looking for.

Keith Over a year ago

I think this answer was so obvious in it's simplicity, that I overlooked it as the solution. :)

Ernest Friedman-Hill · Accepted Answer · 2012-01-12 14:36:03Z

2

I'm not going to write code for this, but

If the list size is a multiple of the max team size, divide by team size to get the number of groups, all of max size, and stop.
Integer-divide the list size by the max team size, then add one. That's the number of groups.
Subtract the list size from that next higher multiple; that's the number of teams that are one less than the max size.

This obviously only works for inputs that are close to working out; it fails if the max team size is large compared to the size of the list.

answered Jan 12, 2012 at 14:36

Ernest Friedman-Hill

81.9k11 gold badges158 silver badges192 bronze badges

Comments

Sergey Kalinichenko · Accepted Answer · 2012-01-12 15:03:22Z

2

If the number of items in the list is N and the max number of items in sublist is K, the solution of your problem comes from solving a Linear Diophantine Equation

K*x + (K-1)*y = N

with additional constraints

x > 0
y >= 0

Where x is the number of sublists of the exact size K, and y is the number of sublists of length K-1.

EDIT : Because of the coefficients to the equation are always off by one from each other, the solution is rather straightforward:

int m = (N+K-1)/K;
int x = N - (K-1)*m; // Number of "full" lists
int y = K*M - N;     // Number of off-by-one lists

Example 1:

N = 31, K = 5
m = (31+5-1)/5 = 7
x = 31 - (5-1)*7 = 3 // 3 lists of 5 items
y = 5*7 - 31 = 4     // 4 lists of 4 items

Example 2:

N = 32, K = 4
m = (32+4-1)/4 = 8
x = 32 - (4-1)*8 = 8 // 8 lists of 4 items
y = 4*8 - 32 = 0     // no lists of 3 items

Look up an algorithm for solving linear Diophantine equations on the net - it is not that complicated, if you understand Euclidean algorithm well. The number of solutions of the equation without constraints is infinite, but once you add the constraints, you should get a single solution.

edited Jan 12, 2012 at 15:03

answered Jan 12, 2012 at 14:42

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

1 Comment

Keith Over a year ago

I think the algorithm changes somewhat based on the example with a list of 31, max size of 10.

andrey · Accepted Answer · 2012-01-12 15:29:14Z

0

public class Q {
public static void q(int size, int maxTeamSize) {
    int numOfTeams = size / maxTeamSize;
    int mod = size % maxTeamSize;
    numOfTeams += (mod > 0) ? 1 : 0;
    System.out.print("\n(" + size + ":" + maxTeamSize + ")");
    for (int i = 0; i < numOfTeams; i++) {
        System.out.print(" " + (size / numOfTeams + ((i < mod) ? 1 : 0)));
    }
}

public static void main(String[] args) {
    q(13, 3);
    q(12, 4);
    q(31, 5);
    q(31, 6);
}
}

answered Jan 12, 2012 at 15:29

andrey

8424 silver badges6 bronze badges

1 Comment

Keith Over a year ago

This is a neat algorithm but results in more groups of a smaller number. I am aiming at getting as many groups as close as possible to the max team size as possible.

Collectives™ on Stack Overflow

Algorithm to partition a list into groups

4 Answers 4

2 Comments

Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related