Kotlin(按顺序)生成没有重复元素的列表的排列 [英] Kotlin generate permutations (in order) of list without duplicate elements

问题描述

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

感谢您的帮助。

推荐答案

Code on play.kotlinlang.org

fun main() {
    val list = listOf('A', 'B', 'C', 'A', 'B', 'D', 'A')
    generatePermutations(list, ::println)
}

/**
 * Generates all permutations described in your question
 * For the sake of performance it calls [onNextPermutation] for each permutation,
 * but it uses the same list to write permutations in,
 * so if you need to use these permutations elsewhere copy its parameter by youself
 */
fun <T> generatePermutations(elementsList: List<T>, onNextPermutation: (List<T>) -> Unit) {
    if (elementsList.isEmpty()) {
        onNextPermutation(emptyList())
        return
    }
    val elementCounts = LinkedHashMap<T, Int>() // We need to remember order in which the elements were added to map
    elementsList.forEach {
        elementCounts[it] = 1 + (elementCounts[it] ?: 0) // Count our elements
    }
    val differentElements = elementCounts.keys
    
    val totalPermutationsCount = elementCounts.values.fold(1) { a, b -> a * b }
    
    // Next 3 collections are reused through generator loop for the sake of performance
    
    val takenEntryNumbers = LinkedHashMap<T, Int>() // Number of entry of each element we will take to next permutation
    differentElements.forEach { takenEntryNumbers[it] = 0 }
    
    val entriesOfElementViewed = HashMap<T, Int>() // Count of entries of each element we already viewed while iterating elementsList
    differentElements.forEach { entriesOfElementViewed[it] = 0 }
    
    val currentPermutation = ArrayList<T>() // Mutable list which we will use to write permutations in
    repeat(differentElements.size) { currentPermutation.add(elementsList[0]) } // Just fill it to needed size
    
    repeat(totalPermutationsCount) { // Generate next permutation
        var entriesTaken = 0 // Total count of entries taken in this permutation
        for (element in elementsList) { // Generate current permutation
            if (entriesOfElementViewed[element] == takenEntryNumbers[element]) {
                currentPermutation[entriesTaken++] = element
            }
            entriesOfElementViewed[element] = 1 + (entriesOfElementViewed[element] ?: 0)
        }
        onNextPermutation(currentPermutation)
        // Update collections to start next permutation
        differentElements.forEach { entriesOfElementViewed[it] = 0 }
        // Generate next permutation of entry numbers, where each entry number is less than element's total count
        for (element in differentElements) { 
            if (1 + (takenEntryNumbers[element] ?: 0) == elementCounts[element]) {
                takenEntryNumbers[element] = 0
            }
            else {
                takenEntryNumbers[element] = 1 + (takenEntryNumbers[element] ?: 0)
                break
            }
        }
        
    }
    
}

输出：

[A、B、C、D]

[B、C、A、D]

[B、C、D、A]

[A、C、B、D]

[C、A、B、D]

[C、B、D、A]

解决了O(listSize*permuationsCount)中每个列表泛型类型的问题

这篇关于Kotlin(按顺序)生成没有重复元素的列表的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！