Kotlin generate permutations (in order) of list without duplicate elements

Question

Is there an easy (and maybe even Kotlin way) to generate all permutations of a given list (containing duplicate elements), which:

• Keeps the order of the elements
• Removes all duplicate elements
• Includes all elements

For example:

Given the list: [A, B, C, A, B, D, A], I would expect the following outcomes:

[A, B, C, D], [A, C, B, D], [B, C, A, D], [C, A, B, D], [C, B, A, A], [B, C, D, A], ... (if there are any more combinations)

The following outcomes are not valid:

[A, B, C, A, D] (duplicate A)

[A, B, C, A] (duplicate A and missing D)

[A, C, D, B] (wrong order)

Thanks for your help.

Answer 1

An Iterator based approach:

fun Int.factorial(): Long {
    require(0 <= this) { "Factorial is undefined for negative numbers." }
    // Not using BigDecimal, so we must fit inside a Long.
    require(this < 21) { "Factorial is undefined for numbers greater than 20." }
    return when (this) {
        0, 1 -> 1L
        else -> (2..this).fold(1L) { acc, i -> acc * i }
    }
}

/**
 * Iterates the permutations of the receiver array.
 * By using an iterator, we minimize the memory footprint.
 */
fun <T> List<T>.permutations(): Iterator<List<T>> {
    // The nth permutation of the receiver list.
    fun <T> List<T>.permutation(nth: Long): List<T> {
        if (isEmpty()) return emptyList()
        val index = (nth % size)
            .also { require(it < Int.MAX_VALUE) }
            .toInt()
        // Grab the first element...
        val head = elementAt(index)
        // ...make a list of what's left...
        val tail = slice(indices.filter { it != index })
        // ...permute it...
        val tailPerm = tail.permutation(nth / size)
        // ...jam it all together.
        return listOf(head) + tailPerm
    }

    val total = size.factorial()
    return object : Iterator<List<T>> {
        var current = 0L
        override fun hasNext(): Boolean = current < total

        override fun next(): List<T> {
            require(hasNext()) { "No more permutations." }
            return this@permutations.permutation(current++)
        }
    }
}


fun main() {
    listOf("0", "1", "2")
        .permutations().withIndex()
        .forEach { (nth, item) -> println("$nth - $item") }
}

And a unit test with some helpers.

// Make lists of ints so we can use checksums.
private fun makeItems(n: Int): List<Int> {
    require(0 < n)
    return (0 until n).toList()
}

fun <K,V> MutableMap<K, V>.mapValue(key: K, f: (V) -> V) {
    put(key, f(getValue(key)!!))
}

    @Test
    fun test() {
        val size = 4
        val items = makeItems(size)
        assert(items.size == size)
        val rowChecksum = (1 until size).sum()
        var totalPermutations = 0L
        // We'll check this histogram of "columns", below.
        val columns = Array(size) { mutableMapOf<Int, Int>().withDefault { 0 } }
        items.permutations().forEach { permutation ->
            ++totalPermutations
            assert(permutation.size == size) { "Permutation has wrong size: ${permutation.size}, expected $size" }
            assert(permutation.sum() == rowChecksum) { "Permutation has wrong sum: ${permutation.sum()}, expected $rowChecksum" }
            (0 until size).forEach { column ->
                columns[column].mapValue(permutation[column]) { it + 1 }
            }
        }
        assert(totalPermutations == size.factorial())
        val expectedFrequency = (size - 1).factorial()
        columns.forEach {column ->
            assert(column.size == size) {
                "Column has wrong size: ${column.size}, expected $size"
            }
            items.forEach { item ->
                assert(column[item]!!.toLong() == expectedFrequency) {
                    "Column has wrong frequency for item $item: ${column[item]}, expected $expectedFrequency"
                }
            }
        }
    }

Answer 2

A perhaps shorter functional way to generate all permutations of a given list:

private fun <E> List<E>.permutations(builtSequence: List<E> = listOf()): List<List<E>> =
    if (isEmpty()) listOf(builtSequence)
    else flatMap { (this - it).permutations(builtSequence + it) }

If you want not to have duplicate elements, it may be best to call .distinct() on the list before you make permutations, like

fun main() {
println(
    listOf("A", "B", "C", "A", "B", "D", "A").distinct().permutations().withIndex()
        .joinToString("\n") { (index, permutation) -> "${index + 1} $permutation" })}

Of course, if you would like to make permutation automatically call distinct, you can make something like

private fun <E> List<E>.distinctPermutations() = distinct().permutations()

However, that may not be a great idea from a code understandability standpoint, as permutations are usually defined as actions on a set, which by its nature does not have duplicate elements (https://en.wikipedia.org/wiki/Permutation).

Answer 3

Try this solution below. Heavily recursive but easy to understand (closest to our thinking). One drawback is mem usage. It's up to you to write a non-recursive one.

fun <T> allPermutations(set: Set<T>): Set<List<T>> {
    if (set.isEmpty()) return emptySet()

    fun <T> _allPermutations(list: List<T>): Set<List<T>> {
        if (list.isEmpty()) return setOf(emptyList())

        val result: MutableSet<List<T>> = mutableSetOf()
        for (i in list.indices) {
            _allPermutations(list - list[i]).forEach {
                item -> result.add(item + list[i])
            }
        }
        return result
    }

    return _allPermutations(set.toList())
}

The input is a set. For your problem, all you need to do is convert your list to a set before calling the method: allPermutations (yourList.toSet())

Answer 4

Extension function which returns all permutations

fun <T> List<T>.permutations(): List<List<T>> = if(isEmpty()) listOf(emptyList()) else  mutableListOf<List<T>>().also{result ->
        for(i in this.indices){
            (this - this[i]).permutations().forEach{
                result.add(it + this[i])
            }
        }
    }

Answer 5

Here's a way to do it in a somewhat functional style.

It starts by collecting a set of "instructions" of the distinct values paired to their occurrence index that should be retained. To do this it maps the unique values to their occurrence counts. Then it folds them into a list of all possible pair combinations. The fold operation starts with an empty set of permutations, and then each unique value multiplies all its possible retained indices with the existing set of permutations.

Then we pass through all the instruction sets to apply the instructions: removing all but one of each unique value from a copy of the original list.

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 }) }
                }
            }
        }
    }
}

I think the complexity is O(n*mⁿ) where n is the number of distinct values and m is the highest repetition of a distinct value. Same as the other answer, since the worst case number of permutations is mⁿ.

Answer 6

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
            }
        }
        
    }
    
}

Output:

[A, B, C, D]

[B, C, A, D]

[B, C, D, A]

[A, C, B, D]

[C, A, B, D]

[C, B, D, A]

Solves your problem for every list generic type in O(listSize * permutationsCount)