The algorithm for splitting the list into groups

Question

I have a list of names.

I want to break this list into groups of a certain size. All groups should be equal to or smaller than the specified size, with the maximum possible group size for the groups and as close as possible to the specified size.

What algorithm (Java-esque pseudo-code, if possible, please!) Determines the most suitable group sizes?

For instance:

The list contains 13 names - the maximum team size is 3. Exit (group sizes): 3, 3, 3, 2, 2

The list contains 13 names - the maximum command size is 4. Exit: 4, 3, 3, 3

The list contains 31 names - the maximum command size is 5. Exit: 5, 5, 5, 4, 4, 4, 4

The list contains 31 names - the maximum size of a command 6. Exit: 6, 5, 5, 5, 5, 5

The list contains 31 names - the maximum command size is 10. Exit: 8, 8, 8, 7

Answer 1

It is pretty simple. You calculate the result of N div M and add 1 to have the correct number of arrays (N is the length of the list, and M is the maximum size of the command), then you iterate over all arrays to add the element until you finish the elements

example: 43 names, the maximum command number is 4 => 43 mod 4 + 1 = 11, there remains 3. so there are 11 arrays (10 with 4 and 1 with 3)

Answer 2

I will not write code for this, but

• If the size of the list is a multiple of the maximum size of the command, divide it by the size of the group to get the number of groups, the entire maximum size and stop.
• Integer - divide the list size by the maximum command size, then add it. This is the number of groups.
• Subtract the size of the list from the next higher multiple; that the number of teams is one less than the maximum size.

This obviously only works for inputs close to development; it fails if the maximum command size is large compared to the size of the list.

Answer 3

If the number of elements in the list is N and the maximum number of elements in the sublist K , the solution to your problem comes from solving the linear diophantine equation

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

with additional restrictions

 x > 0 y >= 0 

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

EDIT: Due to the fact that the coefficients of the equation are always disconnected from each other, the solution is quite simple:

 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 at the algorithm for solving linear Diophantine equations in a network - it’s not so difficult if you understand the Euclidean algorithm well. The number of solutions to the equation without restrictions is infinite, but as soon as you add restrictions, you should get one 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); } }