我们有一个元素列表[A,B,C,D,E]和3组来组合这些元素,我想打印一个列表所有这 3 组都没有重复的独特组合。只有长度为 [2,2,1] 的组才是有效的(可以在之后进行过滤,这不是必须的,但如果需要的话,可以手动将组的长度指定为参数) )。我的意思是独特而不重复:
[[A,B],[C,D],[E]] 和 [[C,D],[A,B],[E]] 和 [[B,A],[C,D] ],[E]] 是相同的,所以组内元素的顺序或组的顺序并不重要,我对这些组合不感兴趣。
在我的特定情况下,我有 16 个项目和 3 组,每组 5、5 和 6 个项目。
我想要实现的目标的一个例子:
/**
* Returns all the unique combinations of a group into multiple groups
* [data] the group of elements to combine
* [numberOfGroups] the number of groups
*/
fun combinations(data: List<String>, numberOfGroups: Int): List<List<List<String>>> {
// The combinations code
}
val data = listOf("A", "B", "C", "D", "E")
print(combinations(data, 3))
输出将是这样的:
[
[[A,B],[C,D],[E]],
[[A,D],[B,C],[E]],
...
]
提前谢谢您。
最佳答案
我一般不知道您的问题的答案,但我会尝试解决将 5 个元素的列表拆分为组 [2, 2, 1] 的特殊情况,并分享一些可能有帮助的原则您可以设计一个更通用的解决方案。
首先我们来谈谈如何表示结果。如果组内元素的顺序不重要,则可以方便地用 Set<String>
表示组。 ,这样 setOf("A", "B")
等于 setOf("B", "A")
。然后,如果组合中组本身的顺序并不重要,则该组合可以是一组组,即 Set<Set<String>>
.
现在谈谈算法本身。将此类算法构造为递归搜索很方便:从数据中选择第一组项目,然后针对没有所选项目的数据求解问题,并将第一组与除它之外的所有解决方案组合起来。所以我们搜索组合的函数可以如下所示:
fun combinationSequence(data: List<String>): Sequence<Set<Set<String>>> = sequence {
for (group in possibleFirstGroups(data)) {
val remaining = data - group
if (remaining.isEmpty()) {
yield(setOf(group))
} else {
yieldAll(combinationSequence(remaining).map { r -> setOf(group) + r })
}
}
}
然后如何以所有可能的方式选择第一组。对于大小为 1 或 2 的组,我们可以从所有数据元素中选择组的第一个元素,然后从剩余的元素中选择第二个元素:
fun possibleFirstGroups(data: List<String>): Sequence<Set<String>> =
when (data.size) {
0 -> emptySequence()
1, 2 -> sequenceOf(data.toSet())
else -> sequence {
for (e1 in data) {
for (e2 in data - e1) {
yield(setOf(e1, e2))
}
}
}
}
我们的combinationSequence
返回结果,但是会有很多重复,比如[[A, B], [C, D], [E]]
和[[C, D], [A, B], [E]]
。为了只保留其中不同的,我们可以使用函数 distinct
:
combinationSequence(data).distinct().forEach { println(it) }
请注意,此解决方案的复杂性随着项目数量呈指数级增长,因此我不希望 16 个元素的解决方案及时终止:)
降低复杂性的一种方法是修剪搜索空间。例如,如果我们已经找到以 [A, B]
开头的所有组合。组,我们可以避免产生在中间某处包含该组的组合,例如 [C, D], [A, B], ...
.
关于java - 将一个组组合成多个组而不重复,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55759517/