Permutations

Algorithms  #algorithms 

In mathematics, a permutation is an arrangement of objects in a specific order. For example, if we have a set of three objects (A, B, and C), there are six possible permutations of those objects: (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), and (C, B, A).

Permutations can be used to solve problems in which the order of the objects is important. For example, if we have a list of words and we want to find all possible combinations of those words, we can use permutations to generate the different combinations.

Permutations can also be used to generate all possible combinations of a given set of elements. For example, if we have a set of numbers and we want to find all possible combinations of those numbers, we can use permutations to generate the different combinations.

In general, the number of permutations of a set of n objects is given by the formula n! (n factorial), where n! = n * (n-1) * (n-2) * ... * 2 * 1. For example, the number of permutations of a set of three objects is 3!, or 6.

• Recursive solution

import java.util.*

//sampleStart
fun main() {
    // click + to see full script
    val arr = "ALAB".toCharArray().toList()
    val result = mutableListOf<List<Char>>()
    permute(arr, 0, arr.size.dec(), result)
    result.also {
        println("Total permutations: ${it.count()}")
    }.forEach(::println)
}
//sampleEnd

fun <T> permute(list: List<T>, left: Int, right: Int, result: MutableList<List<T>>) {
    if (left == right) {
        result.add(list.toList())
    } else {
        val visited = mutableMapOf<T, Boolean>()
        for (i in left..right) {
            if (visited.getOrDefault(list[i], false)) {
                continue
            }
            visited[list[i]] = true
            Collections.swap(list, left, i)
            permute(list, left.inc(), right, result)
            Collections.swap(list, left, i)
        }
    }
}

• Non-recursive solution

import java.util.*

//sampleStart
fun main() {
    // click + to see full script
    Permutations().permute("ALAB".toCharArray().toMutableList()).also {
        println("Total permutations: ${it.count()}")
    }.forEach(::println)
}
//sampleEnd

class Permutations {
    data class Frame<T>(
        val index: Int, var swapCount: Int, var lastVisited: MutableMap<T, Boolean> = mutableMapOf()
    )

    fun <T> swap(list: MutableList<T>, it: Int, to: Int) {
        val tmp = list[it]
        list[it] = list[to]
        list[to] = tmp
    }

    fun <T> permute(list: MutableList<T>): List<List<T>> {

        val solutions = mutableListOf<List<T>>()

        if (list.size == 1) {
            solutions.add(list.toList())
            return solutions
        }

        val stack: Stack<Frame<T>> = Stack()
        stack.push(Frame(index = 0, swapCount = -1))

        while (stack.isNotEmpty()) {
            val f = stack.pop()
            if (f.index.inc() == list.size) {
                solutions.add(list.toList())
            }
            if (f.swapCount > 0) {
                swap(list, f.index, f.index + f.swapCount)
            }

            if (f.swapCount.plus(f.index) != list.size.dec()) {
                stack.push(f)
                f.swapCount++
                val nextSwap = f.index.plus(f.swapCount)
                if (f.lastVisited.getOrDefault(list[nextSwap], false).not()) {
                    f.lastVisited[list[nextSwap]] = true
                    swap(list, f.index, nextSwap)
                    for (i in f.index.inc() until list.size) {
                        stack.push(
                            Frame(
                                index = i, swapCount = 0, lastVisited = mutableMapOf(list[i] to true)
                            )
                        )
                    }
                }
            }
        }

        return solutions

    }
}