是否有一种简单的(甚至可能是 Kotlin 方法)来生成给定列表(包含重复元素)的所有排列,其中:
例如:
鉴于列表:
[A, B, C, A, B, D, A]
,我希望得到以下结果:[A, B, C, D]
, [A, C, B, D]
, [B, C, A, D]
, [C, A, B, D]
, [C, B, A, A]
, [B, C, D, A]
,...
(如果还有更多组合)以下结果无效:
[A, B, C, A, D]
(重复A)[A, B, C, A]
(重复 A 和缺失 D)[A, C, D, B]
(错误的顺序)谢谢你的帮助。
最佳答案
这是一种以有点功能性的风格来做到这一点的方法。
它首先收集一组与应保留的出现索引配对的不同值的“指令”。为此,它将唯一值映射到它们的出现次数。然后它将它们折叠成所有可能的对组合的列表。折叠操作从一个空的排列集开始,然后每个唯一值将其所有可能的保留索引与现有的排列集相乘。
然后我们遍历所有指令集以应用指令:从原始列表的副本中删除每个唯一值中的除一个之外的所有值。
fun <T> getPermutationsWithDistinctValues(original: List<T>): Set<List<T>> {
if (original.isEmpty())
return emptySet()
val permutationInstructions = original.toSet()
.map { it to original.count { x -> x == it } }
.fold(listOf(setOf<Pair<T, Int>>())) { acc, (value, valueCount) ->
mutableListOf<Set<Pair<T, Int>>>().apply {
for (set in acc) for (retainIndex in 0 until valueCount) add(set + (value to retainIndex))
}
}
return mutableSetOf<List<T>>().also { outSet ->
for (instructionSet in permutationInstructions) {
outSet += original.toMutableList().apply {
for ((value, retainIndex) in instructionSet) {
repeat(retainIndex) { removeAt(indexOfFirst { it == value }) }
repeat(count { it == value } - 1) { removeAt(indexOfLast { it == value }) }
}
}
}
}
}
我认为复杂度是 O(n*mn),其中 n 是不同值的数量,m 是不同值的最高重复。与另一个答案相同,因为最坏情况下的排列数是 mn。
关于list - Kotlin 生成没有重复元素的列表的排列(按顺序),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59715608/