算法将列表分成组

我有一个名称列表。算法将列表分成组

我想将此列表分成指定大小的组。所有组应该等于或小于指定的大小，尽可能在组间大小相等，尽可能接近指定的大小。

什么算法（如果可能，请使用Java-esque伪代码！）确定最合适的组大小？

例如：

列表包含13名 - 最大团队尺寸3. 输出（组大小）：3，3,3，2,2

列表包含13名 - 最大团队规模4 。输出：4，3，3，3

列表中包含31名 - 最大团队规模5 输出：5,5，5,4，4,4，4

列表中包含31名 - 团队规模最大为6. 输出：6,5，5,5，5,5

列表中包含31名 - 最大团队规模10 输出：8,8，8,7

来源

2012-01-12 Keith

这功课吗？你有什么尝试？ – 2012-01-12 14:31:42

1,1,1,1,1,1,1,1,1,1,1,1,1在每个组中最多有3个项目，并且组大小比您的示例中的要大。 – Robert 2012-01-12 14:39:41

预期产出不明确。例如，输出是什么：列表包含31个名称 - 最大团队规模10 – 2012-01-12 14:50:19

这很简单。您计算N div M的结果并添加1以获得正确的数组数（N是列表长度，M是最大团队大小），然后在所有数组上迭代以添加项目例如：43个名字，最大球队号码4 => 43 mod 4 + 1 = 11，仍然是3.如此11阵列（10与4以及1与3）

来源

2012-01-12 14:38:31 Grooveek

你可能是指'div'，而不是'mod'，因为'43 mod 4'是'3'，而不是'10'（'mod'的意思是*余数*，不是整数除法）。如果'M'将N除以余数，'+ 1'也不起作用。你需要做'（N + M-1）div M'来获得你正在寻找的结果。 – dasblinkenlight 2012-01-12 15:06:39

你是对的MOD，我洗牌:-D – Grooveek 2012-01-12 15:10:57

我认为这个答案是如此明显，它的简单性，我忽视了它的解决方案。 :) – Keith 2012-01-13 04:37:21

我不会写代码这一点，但

如果列表大小是团队规模最大团队规模，划分的倍数来获得组的数量，所有最大规模的，停止。
整数 - 将列表大小除以最大团队大小，然后添加一个。这是组的数量。
从下一个更高的倍数中减去列表大小;这是比最大规模小一个的团队数量。

这显然只适用于接近工作的输入;如果最大团队规模与列表大小相比较大，则会失败。

来源

2012-01-12 14:36:03

如果列表中的项目数量为N，在子表项的最大数量为K，你的问题的解决方案来自求解Linear Diophantine Equation

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

与附加约束

x > 0 
y >= 0

凡x是确切的大小K的子列表的数目，并且是y长度K-1的子列表的数目。

编辑：由于系数方程总是关闭由一个从彼此，该解决方案是相当简单：

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

实施例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

示例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

在网上查找求解线性丢番图方程的算法 - 如果您理解了 Euclidean algorithm那么它并不复杂。没有约束的方程的解的数量是无限的，但是一旦你添加了约束，你应该得到一个解决方案。

来源

2012-01-12 14:42:23 dasblinkenlight

我认为算法的变化有一些基于31的列表，最大大小为10的例子。 – Keith 2012-01-12 21:08:51

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

来源

2012-01-12 15:29:14 andrey

这是一个整洁的算法，但会导致更多的小组数量。我的目标是尽可能地让尽可能多的团队尽可能接近最大团队规模。 – Keith 2012-01-12 22:20:27

算法将列表分成组

回答

相关问题