java - 将列表随机分组为 N 个子集，每个子​​集有 K 个元素

Question

我有以下列表列表 List<List<Integer>>

1 2
3
4 5 6
7
8
9
10

我必须将此列表列表随机分组为 3 个子集，每个子​​集有 4 个元素（没关系，在最后一个子集中我将有少于 4 个元素），并且在每个子集中我不能有来自同一行的元素（我不能有 3例如 4 5 7）。应该是什么基本算法？？？

Answer 1

应该是什么基本算法？？？

^{从列表列表中的前四个1}随机选择的非空列表中抽取四个随机元素。删除所选项目，然后重复下一个子集。随时删除空列表。

接下来，您需要注意并非所有输入都是可解的：

1
2
3
4
5 6 7 8 9

在这种情况下，我们随机选择

1*
2*
3*
4
5 6 7 8 9*

-> 7 1 2 3（随机选择）

[]
[]
[]
4*
5 6 8 9*

-> 5 4 。. <- 呃，即使非空列表仍然存在，也不可能从不同的列表中选择四个项目。您可以在迭代期间检测到这一点。

¹：或者，如果剩余的非空列表少于四个，则从所有列表中随机选择。

Answer 2

最简单的答案是执行随机选择，检查您的“没有两个来自同一”规则是否被违反。如果是，那就扔掉再试一次。

Answer 3

1. 按元素数量对列表进行排序。

2. 选择 4 个元素，从元素最多的 4 个列表中的每一个中选择一个。

3. 采取。

4. 从 2 开始重复。

堆可以在这里提供帮助。

为什么我们需要从元素最多的列表中挑选？

考虑这种情况：

1 2
3 4
5 6
7
8

如果我们同时选择 7 和 8，我们将得到类似的结果：

1 2
3
5

从这里开始，不可能从不同的列表中选择 4 个元素。

但是，如果我们从具有最多元素的列表中选择元素，我们将得到如下内容：

1
3
5
8

从这里我们可以从每个列表中选择一个元素。