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

Answer 1

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)

Answer 2

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

1. 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.
2. Integer-divide the list size by the max team size, then add one. That's the number of groups.
3. 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.

Answer 3

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.

Answer 4

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);
}
}