Kotlin extension implementation of Heap's Algorithm for generating permutations

permutations.kt

import kotlin.system.measureTimeMillis

fun test_permutations() {
    val list = listOf<Int>(1, 2, 3)
   	val truth_permutations = listOf<List<Int>>(
    	listOf<Int>(1, 2, 3),
        listOf<Int>(2, 1, 3),
        listOf<Int>(3, 1, 2),
        listOf<Int>(1, 3, 2),
        listOf<Int>(2, 3, 1),
        listOf<Int>(3, 2, 1)
    )

    val generated_permutations = list.permutations()
    assert(generated_permutations.size == 6) {
        "Incorrect number of permutations"
    }
        
    for (permutation in truth_permutations) {
        assert(generated_permutations.contains(permutation)) {
            "Permutation missing: ${permutation}"
        }
    }
    
    for (permutation in generated_permutations) {
        assert(truth_permutations.contains(permutation)) {
            "Unexpected permutation: ${permutation}"
        }
    }
}

fun <V> MutableList<V>.swap(index1: Int, index2: Int) {
    val tmp = this[index1]
    this[index1] = this[index2]
    this[index2] = tmp
}

fun Int.isEven() : Boolean {
    return this % 2 == 0
}

fun <V> List<V>.permutations() : List<List<V>> {
    val results: MutableList<List<V>> = mutableListOf()
    
    fun generate(k: Int, list: MutableList<V>) {
        if (k == 1) {
            results.add(list.toList()) 
        } else {
            for (i in 0 until k) {
                generate(k-1, list)
                if (k.isEven()) {
                    list.swap(i, k-1)
                } else {
                    list.swap(0, k-1)
                }    
            }
        }
    }
    
    generate(this.count(), this.toMutableList())
    return results
}


fun profile_permutations() {
    val list: List<Int> = (1..8).map {it}
    val permutations: List<List<Int>>
    val timeInMillis = measureTimeMillis {
        permutations = list.permutations()
    }
    
    println("Generated permutations of size ${permutations.size} in ${timeInMillis} ms")
    // on play.kotlinlang.org this results in "Generated permutations of size 40320 in 75 ms"
}