Recursively calculate permutations in Kotlin

README.md

Overview

I wrote this after coming up short in my searches for a Kotlin implementation of permutations calculation. I ended up adapting a Python solution I found here: https://inventwithpython.com/recursion/chapter6.html

I tried to find a way to do it with tail call recursion but was unsuccessful. This looks like one of those cases where tail call recursion might not be possible or practical.

Developer Notes

I went through several iterations trying to improve the code, learning and re-learning a few things along the way. I'll focus on the recursive part since the base cases that end recursion are pretty straightforward.

In the initial solution (lines 31-37), I had to put acc as the last line of the fold() lambda because it's going to be the value received by acc in the next iteration or returned after the last one.

The acc by itself looked a little funny though, so I tried to eliminate it by using the apply() scope function. According to the Kotlin documentation, apply() returns the context object which, in this case, is acc. So I tried this:

      (0..perm.size).fold(allPerms) { acc, i ->
          acc.apply { add(perm.subList(0, i) + head + perm.subList(i, perm.size)) }
      }

To my surprise, it didn't work. It looked as though the expression evaluated to acc before the apply body is executed. I had no idea why it appeared to behave this way. I tried using the also() scope function and this works:

      (0..perm.size).fold(allPerms) { acc, i ->
          acc.also { it.add(perm.subList(0, i) + head + perm.subList(i, perm.size)) }
      }

This had me really confused so I asked around to see if somebody could tell me what I was missing and folks in r/kotlin came through.

It turned out that instead of binding to the list that permutations() was called on as I assumed it would, head bound to the nearest this, which was the receiver object, acc, itself. Since it was initially empty, the head property getter, which mapped to first(), would throw a NoSuchElementException. I should have paid closer attention to the exception messages.

The lessons learned here are:

1. Closely analyze any exception stack traces you get and understand the reason the exception was thrown.
2. Prefer clear and simple code over cute-sey/clever code.
3. Unlike add() which returns a Boolean, plus() (+) will return a reference to the result. Using plus instead of add was the missing piece of the incantation.
4. Use a profiler if you're unsure about the performance of a certain construct in your code. While immutability is one of the cornerstones of functional programming, there might be a big performance penalty to pay for it.

Someone on Reddit also pointed out that the inner fold() could be simplified by using mapTo, which I liked.

Immutability vs Mutability

The biggest decision I wrestled with in this exercise was whether to use a mutable accumulator with fold() or an immutable one. The immutable accumulator seemed preferable in keeping with the principle of immutability that is the cornerstone of functional programming. However, there was also a concern that it might impact performance from creating many lists over a potentially large number of iterations.

Running both versions through the IntelliJ Profiler, I found that for smaller lists of up to six elements, list creation using listOf was the main bottleneck, which was a little surprising. The recursive step in permutations didn't even get flagged until the list had six elements.

There was a stark difference with lists of eight or more elements though. The immutable version was significantly slower with the degradation increasing exponentially with the number of elements. With ten elements, the mutable list version took 478ms and 51% of time to complete. The immutable version was still going after fifty seconds so I had to stop it. Also, the heap activity plot looked like Donald Trump's signature, with many sharp rises and falls. I can only assume that the valleys were when the garbage collector kicked in.

While I was happy to discover a way to use an immutable accumulator with fold(), in the end I had to go with the mutable version to keep the performance acceptable for larger lists.

Permutation.kt

/**
 * Calculate permutations of elements in a List
 */

// Extension properties 

val <T> List<T>.head: T
    get() = first()

val <T> List<T>.tail: List<T>
    get() = drop(1)

// Extension function
 
fun <T> List<T>.permutations(): List<List<T>> {
    if (isEmpty()) return emptyList()
    if (size == 1) return listOf(this)

    return tail.permutations().fold(mutableListOf()) { acc, perm ->
        (0..perm.size).mapTo(acc) { i ->
            perm.subList(0, i) + head + perm.subList(i, perm.size)
        }
    }
}

// Here are some early versions of the recursive part of the function
// for reference. Improvements were made based on feedback given on r/kotlin
// See the README for link.

    // initial version
    return tail.permutations()
        .fold(mutableListOf()) { allPerms, perm ->
            (0..perm.size).fold(allPerms) { acc, i ->
                acc.add(perm.subList(0, i) + head + perm.subList(i, perm.size))
                acc   // passed to next iteration, returned when done
            }
        }

    // changed inner fold() to mapTo()
    return tail.permutations()
        .fold(mutableListOf()) { allPerms, perm ->
            (0..perm.size).mapTo(allPerms) { i ->
                perm.subList(0, i) + head + perm.subList(i, perm.size)
            }
        }

    // this used an immutable accumulator but performed very poorly
    // on lists with nine or more elements
    return tail.permutations().fold(listOf()) { acc, perm ->
        (0..perm.size).mapTo(mutableListOf()) { i ->
            perm.subList(0, i) + head + perm.subList(i, perm.size)
        } + acc
    }    

PermutationExamples.kt

/* 
 * Examples 
 */
fun main() {
    fun demo(aList: List<Any>) {
        val permutations = aList.permutations()
        println("${aList}.permutations() (size=${permutations.size}) $permutations")
    }
    
    demo(emptyList())        // expected size == 0
    demo(listOf("foo")       // expected size == 1
    demo(listOf('0', '1'))   // expected size == 2
    demo("abc".toList())     // expected size == 6
    demo(listOf(1, 2, 3, 4)) // expected size == 24
}

This is based on code I found at the URL referenced in the comment. I needed it for some Advent of Code puzzles I was working on. The first solutions I wrote were very imperative in nature and I wanted to have something that was more functional. Didn't quite get to a tail-recursive solution but I think this is pretty good as it is.

The extension properties for head and tail were taken from an SO thread I found, which gave me the idea to rework my initial implementation of permutations. See my aoc-2015 repository for more context, Day09 and Day13