A handful of Kotlin permutations

Lately I have been having an enormous fun with the Advent of Code programming challenges. Some of them included NP-hard algorithms like finding a Hamiltonian path or packing a knapsack. To solve those I wrote several brute-force programs that iterated through all combinations to find the right one.

Finally I came to an understanding of how such an algorithm should be written and found it quite enjoyable to code!

In fact I liked the coding part so much that I encourage you to pick your favourite programming language and implement something similar to the code below, even if this language is Python or Scala and its standard library already has combinations() and permutations() functions.

Kode! Sweet Kode!

For quick coding and prototyping my language of choice is Kotlin. it is expressive and powerful, has fast runtime and advanced type system to catch bugs. Kotlin is an object-oriented language (just like Java), allowing quite a bit of generic programming, which I use here to enjoy the algorithm at its highest level of abstraction.

The central point of this solution is interface Circular<T>, representing “something that circulates through all its states”, e.i. it iterates from zero to the its maximum value, then returns back to zero:

Method state() returns the current state of type T, method inc() changes it to the next one. Method isZero() indicates exactly one state (presumably the initial one). Also I found hasNext() being useful, despite it being almost interchangeable with isZero().

This is how Circular<T> could be implemented for numbers:

Also note some Kotlin goodness: val size is a property declaration and a constructor parameter two-in-one. Functions use the so called “statement syntax” with `=` to return a single expression. I even wrote the inc() method in one line since it is so simple. Last but not least, init{} block is a part of the constructor body, so assert(size > 0) effectively checks the value of the parameter on every object creation. This assert saved me a lot of debugging time when it caught a complicated error caused by a method override.

Now let’s implement something that would go through various combinations of its elements:

In order to generate List<E> with all possible combinations of its elements we use a list of “holders” List<H> where H inherits from Circular<E>, thus is able to generate instances of E. You may think of it like of a padlock with combination wheels: to go through all combinations you spin the first wheel till it comes to zero again, then increase the next wheel by one and keep spinning the first. Extending this process to all the wheels you spin them through all possible combinations in order.

A few comments on the code: protected abstract val state will be overridden, allowing to customize the initialisation. That will prove to be useful later. In method inc() I use a forEach{} loop. This is a so called inline function, meaning that its usage generates byte code equivalent to a similar for-loop. It increases readability with zero cost in terms of performance. The same is true about functions all{} and any{}, providing a great example of how readable Kotlin can be. The return statement inside the forEach lambda returns from the inc() method, not the lambda. That allows a very powerful mix of imperative and functional concepts. The it keyword refers to a single lambda parameter. For readability reasons the keyword is not applicable when a lambda has two or more parameters, so you have to name the parameters explicitly.

In this post I work with combinations of integers and lists of integers, so I found it useful to have a specialised version of CircularList<E, H> just for that:

I used Ring as the holder class since it circulates through numbers, which is exactly what we need. By the way, the class has no visible body marked with {}. Don’t worry, it is totally normal in Kotlin to omit it.

Now we have the necessary infrastructure to start building combinations and permutations we wanted from the beginning. Here is a simple one: all possible combinations of bits in a binary number of size N:

We fill state with rings of size 2, which means they will be switching between 0 and 1, just as we wanted. Method state() converts the internal state into a list of integers. Additionally it reverses the list so that the output would look like usual numbers, smaller bits being on the right.

Coincidentally, BinaryBits is a major component for a brute-force Knapsack problem solution. To brute-force the Hamiltonian path problem we’ll need a generator of permutations:

The code in init block fills state with rings of sizes from N down to 1. This a direct result of how we build a permutation: N possibilities for the first position, N - 1 possibilities for the second position, and so on.

We are almost done with coding, only a finishing touch left: to make Circular<T> implement Iterable<T> so that the standard infrastructure would work with it:

Here we go “full Java” and implement a method iterator() which returns an instance of an anonymous class inherited from Iterator<T> where we override methods next() and hasNext(). Phew! Field started is a hack which makes the iterator start with zero, which it wouldn’t do otherwise. An interesting element in the snippet in the label syntax this@Circular. In a position when several this references are available, one can specify which this he or she means. This goes even farther, allowing you to, say, break a specific loop in the scope, thus returning from a bunch of nested loops with ease.

Finally, after all the hard work let’s check how the parts fit together:

Perfect! Our classes generate iterables, which we can filter, transform and put in for-loops. But be careful to convert an iterable into a sequence with asSequence() before you work with it, or it will be creating a huge list after every operation with intermediate results. All collection operations on Iterable<T> are eager in Kotlin to prevent unpleasant surprises in a multithreaded environment.

The fruits of the hard work

If you are like me and hate reading about somebody else’s code, I have a farewell gift for you. This link should lead to your own copy of the code above, coupled with syntax highlighting, web UI, compiler, type checking and code completion on CTRL+SPACE! Isn’t it wonderful?

Also here is the full code in one Github gist.

Feel free to play/check/run/modify all you want, write me back if you have insightful ideas on the topic!

Thinking differently

One of the reasons I started this blog post was a question from StackOverflow. It asked about a way to implement permutations in Scala. The proposed implementations differed, but to my surprise they all used recursion and other FP technics, and no one considered an imperative solution like the above.

It seems to be a powerful trend in Scala community (and many other communities too) to prefer FP with immutable data structures over the good old OOP with changing state. This approach has its undeniable benefits, but it also has important drawbacks. In my opinion those two approaches should compliment each other in an application and be used depending on the task at hand.

For the task of generating a sequence of permutations the imperative paradigm is arguably better than the functional one in a number of ways (memory footprint, for example). And still no one suggested it as an option in the SO question. Scala has all the imperative tools Kotlin has, if not more, so the language support is not the issue. The problem I see is the “immutable is better than mutable” cliche, and people applying it everywhere, using languages in ways they were not design to work.

I hope this ultra-FP movement will not infect Kotlin and its infrastructure, keeping it in the scope it is today: a pragmatic OOP language with strong functional support for writing clear and efficient code.