Kotlin - favorite

KotlinFavorite.kt

/**
 * List literals and List.get extensions
 */

object L {
    // L[1,2,3,4]
    inline operator fun <T> get(vararg a:T): List<T> = listOf(*a)
}

// aList[0..3]
// aList[0 until 3]
inline operator fun <T> List<T>.get(range: IntRange) : List<T> = slice(range)

// aList[3 downTo 0]
inline operator fun <T> List<T>.get(range: Iterable<Int>) : List<T> = slice(range)

/**
 * A succinct (but not very efficient) quick sort. The line:
 * <pre>drop(1).partition { it <= pivot }</pre> 
 * is particularly expensive as drop() generates a new list and partition() two more.
 * Also the choice of pivot is very naive.
 */
fun <T : Comparable<T>> quickSort(list: List<T>): List<T> =
        with(list) {
            if (size < 2) this
            else {
                val pivot = first()
                val (smaller, greater) = drop(1).partition { it <= pivot }
                quickSort(smaller) + pivot + quickSort(greater)
            }
        }

/**
 * A succinct (but not very efficient) power set implementation.
 * Can be made tail recursive. Funnily having the set argument being of type Set introduces 
 * some complications.
 */
fun <T> powerset(set: Collection<T>): Set<Set<T>> =
        if (set.isEmpty()) setOf(emptySet())
        else {
            powerset(set.drop(1)).let {
                it + it.map { it + set.first() }
            }
        }


/**
 * All permutations of {0..n-1} so that
 * permutations(3) = [[2, 1, 0], [1, 0, 2], [0, 2, 1], [1, 2, 0], [2, 0, 1], [0, 1, 2]]
 */
typealias Permutation = List<Int>

fun permutations(n: Int): List<Permutation> {
    fun insert(element: Int, perm: Permutation): List<Permutation> =
        (0..perm.size).map { perm.drop(it) + element + perm.dropLast(perm.size - it) }

    fun permutations(perm: Permutation): List<Permutation> =
        when (perm.size) {
            0 -> listOf(emptyList())
            else -> permutations(perm.drop(1)).flatMap { p -> insert(perm.first(), p) }
        }

    return permutations(List(n) { i -> i })
}

/**
 * Binary search
 */
tailrec fun binSearc(a: IntArray, l: Int = 0, r: Int = a.size-1, v: Int): Int {
    if (r >= l) {
        return (l + (r - l) / 2).let {
            when {
                v < a[it] -> binSearc(a, l, it - 1, v)
                v > a[it] -> binSearc(a, it + 1, r, v)
                else -> it
            }
        }
    }
    return (-l - 1)
}

/**
 * Fibonacci recursive and O(n)
 */
fun fib(
    n: Int,
    seq: MutableMap<Int, Int> = mutableMapOf(0 to 0, 1 to 1)
): Int =
    seq.getOrPut(n) {
        seq.getOrPut(n - 1) { fib(n - 1) } + seq.getOrPut(n - 2) { fib(n - 2) }
    }

/**
 * Binomial coefficent
 */  
fun binomial(n: Int, k: Int): BigInteger {

    val map = mutableMapOf<Pair<BigInteger, BigInteger>, BigInteger>()

    fun binomial(x: Pair<BigInteger, BigInteger>): BigInteger {
        val (n, k) = x
        if (k == ZERO || n == k) {
            return ONE
        }
        return map.getOrPut(x) { binomial(Pair(n - ONE, k)) + binomial(Pair(n - ONE, k - ONE)) }
    }

    return binomial(Pair(n.toBigInteger(), k.toBigInteger()))
}

/** Cartesian product **/
fun cproduct(vararg data: Iterable<Any>): List<List<String>> = cproduct(data.asList())
fun cproduct(data: List<Iterable<Any>>): List<List<String>> =
    when (data.size) {
        1 -> data.first().map { listOf("$it") }
        else -> {
            val head = data.first()
            val res = cproduct(data.drop(1))
            head.flatMap { h -> res.map { r -> r + "$h" } }
        }
    }