将列表分组的算法

Question

我有一个名字列表。

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

哪种算法（如果可能请提供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

- Keith

---

这是作业吗？你尝试过什么？ - Reverend Gonzo

1,1,1,1,1,1,1,1,1,1,1,1,1 还有每组最多3个项目，而且组大小比你的例子更均等。 - Robert

预期输出不清晰。例如，对于“列表包含31个名称-最大团队大小为10”，输出是什么并不清楚。 - Óscar López

Answer 1

这很简单。您需要计算 N div M 的结果并加1，以得到正确的数组数量（其中N是列表长度，M是最大团队大小），然后您需要在所有数组上进行迭代，直到用完所有项目。

例如：43个名称，最大团队数为4 => 43 mod 4 + 1 = 11，余数为3。因此有11个数组（10个包含4个项目，1个包含3个项目）。

- Grooveek

---

你可能想用 div 而不是 mod，因为 43 mod 4 的结果是 3 而不是 10（mod 表示取余数，而不是整除）。此外，如果 M 可以整除 N，那么 +1 是行不通的。你需要使用 (N+M-1) div M 才能得到你想要的结果。 - Sergey Kalinichenko

我认为这个答案非常简单明了，以至于我忽略了它作为解决方案的可能性。 :) - Keith

Answer 2

如果列表中的项数为N，子列表中的最大项数为K，则您的问题的解决方案来自于解决一个线性不定方程。

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

在网上查找解决线性丢番图方程的算法——如果您很好地理解欧几里得算法，它并不那么复杂。没有限制条件的方程的解数是无限的，但是一旦添加了限制条件，您应该得到一个单一的解。

(Note: I have translated the text into simplified Chinese.)

- Sergey Kalinichenko

---

我认为算法会根据一个包含31个元素，最大长度为10的列表示例而略有改变。 - Keith

Answer 3

我不会为此编写代码，但是

1. 如果列表大小是最大团队大小的倍数，则将其除以团队大小以获取所有最大大小的组数，并停止。
2. 将列表大小整除以最大团队大小，然后加1。这就是组数。
3. 从下一个更高的倍数中减去列表大小；这是小于最大大小的团队数量。

显然，这仅适用于接近有效的输入；如果最大团队大小与列表大小相比较大，则失败。

- Ernest Friedman-Hill

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

- andrey

---

这是一个不错的算法，但会导致更多数量较小的组。我的目标是尽可能接近最大团队大小的数量来得到尽可能多的组。 - Keith