Calculating Permutations (Kotlin)

[Junilu Lacar]

I've been trying to extract some code that calculates permutations that I used in a couple of Advent of Code problems (still working AoC 2015)

I created a Gist with the details of what I learned. https://gist.github.com/jlacar/18345c1802260cd4361090be9c4cebb4 - This gist also includes some code that exercises the function.

Here's the code that worked:

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

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

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

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

To try to tighten up the code in the inner fold operation, I tried using the apply() scope function but was surprised to find that it didn't work (my previously working code and tests failed).

I tried using also and it worked. I don't know what the difference is with apply though because my understanding is that both also and apply return the context object. I assumed that value returned by apply was the context object after the body of apply executed but since it made previously working code fail, I guess I was wrong.

Here's the code that used `also` that worked:

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

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

The code that uses `apply` that DIDN'T work:

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

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

Any thoughts?

[Junilu Lacar]

I posted the question on r/kotlin and someone pointed out that head binds to the nearest this and that was what was causing the different behavior with apply. Makes perfect sense now.

They also pointed out that mutating something inside a fold is not good practice... I'm seeing that now.

I think I had at one point a version that used a forEach as the same person suggested, so I'll probably go back to that, or use mapTo as a second person suggested. Those like good alternatives to the inner fold.

I'll update my gist accordingly.

[Junilu Lacar]

I'm going with this alternative:

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

I switched back to acc for the accumulator parameter because I think it will be familiar to most readers. Should I stick with the intention-revealing name allPerms?

[Junilu Lacar]

Since the above still mutates that fold accumulator, I thought I'd try something that didn't do that at all and this is what I got:

fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    val allPerms = mutableListOf<List<T>>()    return tail.permutations()        .forEach { perm ->            (0..perm.size).mapTo(allPerms) { i ->                perm.subList(0, i) + head + perm.subList(i, perm.size)            }        }.let { allPerms } }
Doesn't seem any better to me though. To fold with a mutable or not to fold with a mutable, that is the question. What do you folks think?

[Piet Souris]

My worry with these things is that if you work with immutable collections, that you get a lot of them while doing the stuff. I don't know if that is a bad thing or not, but I prefer simple mutable collections. That may not be functional, but then I'm not a functional programmer.

In scala I liked that if you add an element to a list, then the result is t :: list, and so you reuse the old list.

I must say that I find your code a bit hard to read, but my unfamiliarity with Kotlin may be the cause of that.

This is an old method that I used (java), and I think it does more or less the same as your code. The problem with java is that when you mutate a collection, you get a boolean instead of the mutated collection. You can't have 'm all. I do not check for an empty input-list, since in that case the IntStream does nothing.

public static <T> List<List<T>> permutaties(List<T> list) {
    var result = new ArrayList<List<T>>();
    if (list.size() == 1) result.add(list);
    else {
        IntStream.range(0, list.size()).forEach(i -> {
            var temp = permutaties(remove(list, i));
            temp.stream().forEach(d -> d.add(list.get(i)));
            result.addAll(temp);
        });
    }
    return result;
}

public static <T> List<T> remove(List<T> list, int index) {
    var result = new ArrayList<>(list.subList(0, index));
    result.addAll(list.subList(index + 1, list.size()));
    return result;
}

As an aside, there was this topic about Wordfeud, where the problem was to generate not all permutations, but all combinations (say all subsets of the input. Carey presented a surprisingly simple way, and I presented a recursive way. If you like to give it a read:    permutations and combinations

[Junilu Lacar]

Another way to do this without getting too cutesey:

fun <T> List<T>.permutations(): List<List<T>> {    if (isEmpty()) return emptyList()    if (size == 1) return listOf(this)    val allPerms = mutableListOf<List<T>>()    tail.permutations().forEach { perm ->         (0..perm.size).mapTo(allPerms) { i ->             perm.subList(0, i) + head + perm.subList(i, perm.size)         }    }    return allPerms }
But that's basically the fold()-with-mutable version with a couple extra lines.

[Junilu Lacar]

Piet Souris wrote:My worry with these things is that if you work with immutable collections, that you get a lot of them while doing the stuff.

I'm fairly confident that with languages that have garbage collection, working with immutable collections in a function like fold() is not an issue. Immutability is a cornerstone of functional programming, so any language that supports functional programming constructs would presumably find a way to make reasonable optimizations.

[Junilu Lacar]

I think I'll go with this version that keeps things immutable in the fold():
   return tail.permutations()        .fold(listOf()) { acc, perm ->            (0..perm.size).mapTo(mutableListOf()) { i ->                 perm.subList(0, i) + head + perm.subList(i, perm.size)            } + acc        }

[Junilu Lacar]

Piet Souris wrote:The problem with java is that when you mutate a collection, you get a boolean instead of the mutated collection.

Not surprisingly, Kotlin has a very similar behavior for its add() function. Luckily, there's also the plus (+) operation, which returns a List when used with lists. This is why the last version of my code that I posted works, because the last expression in the fold() body is the result of plus-ing a list of new permutations and the permutations already in the accumulator acc.

[Piet Souris]

Thanks, Junilu! A very interesting topic indeed.

[Junilu Lacar]

More lessons learned: The person who keyed me in on the problem with head also pointed out that using an immutable list for the accumulator in the fold() could impact performance significantly. So, like any responsible programmer   , I ran my code through a profiler.

The results for larger lists was quite illuminating. For smaller lists (up to 6 elements in my tests), the recursive step wasn't even flagged as the biggest bottleneck. What got flagged instead was the initial creation of the lists themselves, that is, the call to listOf(), especially the first few ones in a series of calls to listOf() I had in my main() function.

The recursive call did get flagged as the main bottleneck when I tried it with a larger list, 10 elements (3,628,800 permutations).

The version that used fold(mutableListOf()) took 508ms at the recursive call, taking 53% of the entire run time.

I had to stop the version that used fold(listOf()) { ... + acc } after 50+ seconds because it was getting ridiculous. I tried with just 9 elements (362,880 permutations) and it took the recursive part 3,398ms and 89% of the entire run time. The mutable list version with 9 elements took 70ms and 47% of the time at the recursive step, but again, the listOf in main() to create the original list was flagged as the main bottleneck, clocking in at 90ms and 60% of the time.

It looks like performance for the immutable version definitely degrades much faster (exponentially?) as the list size increases.

Based on this, I'm reverting to using a mutable accumulator for the fold().

[Junilu Lacar]

Junilu Lacar wrote:

Piet Souris wrote:My worry with these things is that if you work with immutable collections, that you get a lot of them while doing the stuff.

I'm fairly confident that with languages that have garbage collection, working with immutable collections in a function like fold() is not an issue. Immutability is a cornerstone of functional programming, so any language that supports functional programming constructs would presumably find a way to make reasonable optimizations.

By running the code through the profiler, I proved myself wrong here and confirmed Piet's fear

[Youssef Shoaib]

Here's how I'd write it in modern Kotlin (also solving the issue in these examples where `emptyList().permutations.size == 0` but 0 factorial should be 1:
```
private fun <T> List<T>.permutations(): List<List<T>> = if (isEmpty()) listOf(this)
else buildList {
 [email protected]().permutations().forEach { perm ->
   (0..perm.size).forEach { i ->
     val newPerm = perm.toMutableList()
     newPerm.add(i, [email protected]())
     add(newPerm)
   }
 }
}
```