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 * m ⁿ ), где n - число различных значений и m - наибольшее повторение определенного значения. То же, что и в другом ответе, поскольку число перестановок в худшем случае равно m ⁿ .

Answer 2

Код на 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]

Решает вашу проблему для каждого списка обобщенно c введите O (listSize * permutationsCount)