list - Kotlin 生成没有重复元素的列表的排列(按顺序)

Question

是否有一种简单的(甚至可能是 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] (错误的顺序)

谢谢你的帮助。

Answer 1

这是一种以有点功能性的风格来做到这一点的方法。

它首先收集一组与应保留的出现索引配对的不同值的“指令”。为此，它将唯一值映射到它们的出现次数。然后它将它们折叠成所有可能的对组合的列表。折叠操作从一个空的排列集开始，然后每个唯一值将其所有可能的保留索引与现有的排列集相乘。

然后我们遍历所有指令集以应用指令:从原始列表的副本中删除每个唯一值中的除一个之外的所有值。

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。