Combination Generators in Scala

In this article algorithms for generating permutations and combinations are presented and discussed. Push-style and pull-style approaches are presented and discussed, centered around Scala implementations. The conversion between push-style and pull-style implementations is discussed, and the Scala Limited Continuations construct is presented and elaborated upon to build pull-style generator functions. An example is given of the manual conversion of a push-style generator into a pull-style generator, without language constructs like Limited Continuations (Scala) or yield (Python and ES6). Performance aspects of various solutions in Scala and Java are given. The relationship between the various push-style and pull-style generators and the ReactiveX framework is discussed. All source code is available on GitHub.

Who does not remember the formulas for calculating the number of permutations and combinations of a given set of elements? Anyone who has taken some courses math or probability calculus after high school has once met these formulas and the theory behind them. The formulas and their explanations can be found on countless websites. I am not going to repeat the basics of permutations and combinations but I want to tell and demonstrate something about programming with permutations and combinations. For the sake of brevity I will only use the word combinations, permutations being ordered combinations.

Programmatic solutions of various problems require the availability of the set of combinations of elements of a given set. We distinguish between combinations with and without ordering (combinations with ordering also known as permutations) and we distinguish between combinations with and without repetition. As a quick reminder: consider the set {1, 2, 3} and combinations of two elements from this set. All combinations…

  • with ordering and with repetition: { [1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3] },
  • with ordering without repetition: { [1,2], [1,3], [2,1], [2,3], [3,1], [3,2] },
  • without ordering with repetition: { [1,1], [1,2], [1,3], [2,2], [2,3], [3,3] },
  • without ordering without repetition: { [1,2], [1,3], [2,3] }.

To use a set of combinations programmatically, it is possible to generate a list with all combinations. Usually this is not a good idea because this list can be very long. The number of combinations is in all cases in some way exponential in the size of the underlying set. Generating all of them in a list will usually consume a lot of memory, probably more than what one has available. Generating all combinations in advance also means that too much is generated when one looks for a specific combination, and that combination is found somewhere in the front part of the list.

A better idea is to build a generator function that accepts a callback and that generates internally all combinations and invokes the callback with each of the generated combinations. The callback function is the worker function that does something with a single combination. This solution requires a programming language that permits functions as parameters. Programming languages like Scala and newer version of Java will do. Older versions of Java can also be used, when one defines an interface for the callback function, and pass the function as an object of a class that implements this interface. Examples will follow.

Programming these generator functions is fun and an implementation in Scala will be given and discussed for all four variants of combinations. Again, all source code is available on GitHub. By the way, at least the generation of permutations and combinations without repetition is available as standard List functionality in the Scala 2.12.3 Standard Library. I haven’t been able to find the variants “with repetition” as standard functions of List, but maybe they are available in other ways, or they will become available in future versions.

Ordered combinations with repetition:

def repeatingPerm[T](elems: List[T], genSize: Int, f: List[T] => Unit): Unit = {
    def repeatingPermRec(elems: List[T], depth: Int, partResult: List[T]): Unit = depth match {
        case 0 => f(List())
        case 1 => for (elem <- elems) f(elem :: partResult)
        case n => for (elem <- elems) repeatingPermRec(elems, depth - 1, elem :: partResult)
    }
    if (genSize < 0) throw new IllegalArgumentException("Negative lengths not allowed in repeatingPerm...")
    repeatingPermRec(elems, genSize, Nil)
}

Ordered combinations without repetition:

def nonRepeatingPerm[T](elems: List[T], genSize: Int, f: List[T] => Unit): Unit = {
    def removeElem(elems: List[T], elem: T): List[T] = elems match {
        case Nil => Nil
        case head :: tail => if (head == elem) removeElem(tail, elem) else head :: removeElem(tail, elem)
    }
    def nonRepeatingPermRec(elems: List[T], depth: Int, f: List[T] => Unit, partResult: List[T]): Unit = depth match {
        case 0 => f(List())
        case 1 => for (elem <- elems) f(elem :: partResult)
        case n => for (elem <- elems) nonRepeatingPermRec(removeElem(elems, elem), depth - 1, f, elem :: partResult)
    }
    if (genSize < 0) throw new IllegalArgumentException("Negative generation sizes not allowed in nonRepeatingPerm...")
    if (genSize > elems.size) throw new IllegalArgumentException("Generation sizes over elems.size not allowed in nonRepeatingPerm...")
    nonRepeatingPermRec(elems, genSize, f, Nil)
}

Unordered combinations without repetition:

def nonRepeatingComb[T](elems: List[T], genSize: Int, f: List[T] => Unit): Unit = {
    def nonRepeatingCombRec(elems: List[T], depth: Int, partResult: List[T]): Unit = {
        if (elems.size == depth) f(elems.reverse ::: partResult)
        else {
            if (!elems.isEmpty) {
                nonRepeatingCombRec(elems.tail, depth, partResult)
                if (depth > 0) nonRepeatingCombRec(elems.tail, depth - 1, elems.head :: partResult)
            }
        }
    }
    if (genSize < 0) throw new IllegalArgumentException("Negative generation sizes not allowed in nonRepeatingComb...")
    if (genSize > elems.size) throw new IllegalArgumentException("Generation sizes over elems.size not allowed in nonRepeatingComb...")
    nonRepeatingCombRec(elems.reverse, genSize, Nil)
}

Unordered combinations with repetition:

def repeatingComb[T](elems: List[T], genSize: Int, f: List[T] => Unit): Unit = {
    val elemsReverse = elems.reverse
    def folder(triple: (List[T], Int, List[T]), index: Int): (List[T], Int, List[T]) = triple match {
        case (elems, i, result) => (elems.drop(index - i), index + 1, elems.drop(index - i).head :: result)
    }
    def mapSimulation(input: List[Int]): List[T] = (((elemsReverse, 0, Nil: List[T]) /: input) (folder))._3
    def nonRepeatCombRec(elems: List[Int], depth: Int, partResult: List[Int]): Unit = {
        if (elems.size == depth) f(mapSimulation(partResult.reverse ::: elems))
        else {
            if (!elems.isEmpty) {
                nonRepeatCombRec(elems.tail, depth, partResult)
                if (depth > 0) nonRepeatCombRec(elems.tail, depth - 1, elems.head :: partResult)
            }
        }
    }
    if (genSize < 0) throw new IllegalArgumentException("Negative generation sizes not allowed in repeatingComb...")
    val simulationSize = genSize + elems.length - 1
    nonRepeatCombRec((0 until simulationSize).toList, genSize, Nil)
}

The four presented generator functions do nothing except calling the callback with all specified combinations. This might not be the best construction for the solution of a given problem. Many variations on generator functions are possible. Consider for instance a worker (callback) function that delivers a boolean. The generator can be made such that it stops at finding the first combination for which the callback delivers true, and the generator can then deliver this combination. Or the generator can deliver a list of all permutations / combinations for which the callback delivers true. The generation function variant that stops as soon as the callback delivers true has real added value, as this behaviour cannot be simulated with a properly designed callback. Generating a result list with certain combinations is something that can be done with a cleverly designed callback (just let the callback accumulate the desired list in a global variable). Stopping the generation at a certain point might be desirable if the entire set is too large to process in its entirety.

As an example a variant of the generator function for unordered combinations without repetition that stops when the callback delivers true for the first time and deliveres this first combination for which the callback delivers true.

def nonRepeatingCombSeekFirst[T](elems: List[T], length: Int, f: List[T] => Boolean): Option[List[T]] = {
    def nonRepeatingCombSeekFirstRec(elems: List[T], length: Int, partResult: List[T]): Option[List[T]] = {
        if (elems.size == length) {
            val result = elems.reverse ::: partResult
            if (f(result)) Some(result) else None
        }
        else {
            if (!elems.isEmpty) {
                nonRepeatingCombSeekFirstRec(elems.tail, length, partResult) match {
                    case None => nonRepeatingCombSeekFirstRec(elems.tail, length - 1, elems.head :: partResult)
                    case x => x
                }
            }
            else None
        }
    }
    if (length < 0) throw new IllegalArgumentException("Negative lengths not allowed in nonRepeatingCombSeekFirst...")
    if (length > elems.size) throw new IllegalArgumentException("Lengths over elems.size not allowed in nonRepeatingCombSeekFirst...")
    nonRepeatingCombSeekFirstRec(elems.reverse, length, Nil)
}

The order in which the combinations are delivered by these generator functions might be relevant to the solution of a certain problem. Often the number of combinations is too big to permit an exhaustive treatment of all possibilities. In that case one might want to confine oneself to a subset of all combinations, and chose this subset such that the optimal combination is most likely in the subset. We enter the field of heuristic algorithms here. Even in the case that an exhaustive treatment of all possibilities is unavoidable, it might be sensible to chose the generation ordering such that the sought after optimal combination is most likely in the beginning of the sequence, thereby saving computation time.

Ordering of the generation is influenced by the details of the generation algorithm and by the ordering of the supplied underlying set of elements. Therefore this set is always given as a list in the above algorithms. Generated combinations are also passed to the callback in a list, although an unordered combination could be represented with a set. There can always be secundary or non-functional requirements that could be met by not throwing away ordering that emerges from the use of a certain algorithm.

The generator for unordered combinations without repetition for instance is designed such that the algorithm favours combinations from elements from the beginning of the supplied set (as list). Generating combinations of three elements from the set [A, B, C, D, E F] will proceed in the following order: [A, B, C], [A, B, D], [A, C, D], [B, C, D], [A, B, E], etc. First all combinations from [A, B, C] will be given (that’s only one), then all (remaining) combinations from [A, B, C, D] will be given (three of them), then all (remaining) combinations from [A, B, C, D, E], etc. This is useful when one wants to favour, or to consider first, combinations from elements from the front part of the underlying set. The ordering of the elements in the combinations reflects the ordering of the underlying set. To achieve this, there are various calls of reverse on lists in the generator algorithm (two seemingly superfluous calls). If the various aspects of ordering are not relevant, these calls of reverse can be removed, since they do slow down the algorithm a little bit.

Instead of a generator algorithm and callback functions, it is possible to build a stream-like generator that provides a specified set of combinations. The diffence with the design described above is the difference between push-processing and pull-processing. The generator with callbacks will push combinations into the callback function. A stream-like generator would offer a next() and hasNext() method with which the combinations can be pulled from the generator. With next() and hasNext() we have in fact an iterator that can conveniently be used in program constructions like the Scala for-statement.

It is very easy to construct a push-generator, given a pull-generator:

def constructPushGenerator(callback: (List[T] => Unit), iterator: Iterator[List[T]) = for (lst <- iterator) callback(lst) 

It is not so easy to construct a pull-generator, given a push-generator. Therefore, a pull-generator seems the most desirable one. The problem lies in the fact that one wants to avoid to construct in advance a list with all combinations that are subsequently pulled from the list. The construction of such a list in advance would often be not acceptable for performance reasons. Such an implementation will potentially suffer from an unacceptable memory footprint and from an unacceptable startup delay. We are looking for a way to generate a combination “just in time” at the moment it is needed at a call of next(). To be able to generate the next combination, the algorithm has to maintain a state that corresponds to the last generated combination and that can be advanced easily to the next combination. For some algorithms this is easy to work out. Consider an algorithm for generating ordered combinations with repetition. This is in fact N-ary counting with N the number of elements in the underlying set. The state to be maintained in a pull-type generator is just the last generated combination. To generate the next combination, take the last combination, advance the least-significant, fastest changing position one element and transport a “carry” to the next position when one reaches the end.

class RepeatingPermPull[T](domain: List[T], genSize: Int)  extends Iterable[List[T]] {
    val mod = domain.length
    var hasNextVar = (mod > 0 || genSize == 0)
    val status = Array.fill(genSize)(0)

    def progress() = {
        var carry = true
        var index = 0
        while (carry && index < genSize) { status(index) += 1 carry = false if (status(index) >= mod) {
                status(index) = 0
                carry = true
                index += 1
            }
        }
        hasNextVar = index < genSize
    }

    def iterator = new Iterator[List[T]] {
        def hasNext(): Boolean = hasNextVar
        def next(): List[T] = {
            val result = status.map(domain(_)).toList
            progress()
            result
        }
    }
}

For other algorithms this might not be so easy. Take for instance the algorithm for generating unordered combinations without repetition. The recursive, push-style generator algorithm given above (nonRepeatingComb), can fire two recursive calls in the course of one invocation. The two recursive calls do look asymmetric in the sense that lengths of list parameters of both calls are different and also the result of the calls are processed differently. The state that is responsible for generating a certain combination is in fact the state of the call stack of the sequence of recursive calls that lead to a certain combination. It seems not to be easy to write an imperative solution for this problem, like the imperative while-loop solution for the ordered combinations with repetition. It is possible to simulate the state on the call stack in an imperative algorithm. With a little bit knowledge of compiler technology it is possible to create an imperative algorithm that keeps the same state information on an explicitly managed stack as what the recursive algorithm does with the implicit call stack. The explicit stack can be kept in memory between successive calls to next(). This enables us to realize a pull-style generator.

class NonRepeatingCombPull[T](domain: List[T], genSize: Int)  extends Iterable[List[T]] {
    case class StackFrame(partDomain: List[T], curSize: Int, partResult: List[T], callOrder: Int)
    class MyStack[T] {
        private var rep: List[T] = Nil
        def push(t: T) = rep = t :: rep
        def pop() = rep = rep.tail
        def top() = rep.head
        def empty() = rep.isEmpty
    }
    var hasNextVar = true
    var stack = new MyStack[StackFrame]()
    stack.push(StackFrame(domain.reverse, genSize, Nil, 2))
    var callOrder = 0
    def progress() = {
        if (stack.top.partDomain.size == stack.top.curSize) callOrder = 3
        else callOrder = 1
        if (stack.top.curSize == 0 && callOrder == 2) callOrder = 3
        do {
            if (stack.top.partDomain.isEmpty) callOrder = 3
            if (stack.top.curSize == 0 && callOrder == 2) callOrder = 3
            callOrder match {
                case 1 => {
                    stack.push(StackFrame(stack.top.partDomain.tail, stack.top.curSize, stack.top.partResult, 1))
                }
                case 2 => {
                    stack.push(StackFrame(stack.top.partDomain.tail, stack.top.curSize - 1, stack.top.partDomain.head :: stack.top.partResult, 2))
                    callOrder = 1
                }
                case 3 => {
                    callOrder = stack.top.callOrder + 1
                    stack.pop()
                    hasNextVar = !stack.empty()
                }
            }
        } while (hasNextVar && stack.top.partDomain.size != stack.top.curSize)
    }
    def iterator = new Iterator[List[T]] {
        def hasNext(): Boolean = hasNextVar
        def next(): List[T] = {
            val result = stack.top.partDomain.reverse ::: stack.top.partResult
            progress()
            result
        }
        progress()
    }
}

I have made a straight forward translation of the recursive generator function above (nonRepeatingComb). Maybe it can be optimized a little bit here and there, but I don’t see other solutions to this problem that do not have state information that somehow resembles the information on the call stack of a recursive solution. It is evident therefore that this problem is best solved with recursion. The field callOrder in StackFrame corresponds to the return address in real stack frames. In this algorithm, each invocation may give rise to two subsequent recursive invocations. One has to keep track of what call did originate where, to be able to continue after the completion of a recursive call.

Of course this algorithm looks clumsy. The recursive algorithm (nonRepeatingComb) is concise and elegant; the imperative mimicking of recursion with an explicit call stack is way more complex and difficult to get right. The programming language Python has a construct that enables one to convert a push-style generator in a pull-style generator with minimal effort (newer versions of JavaScript, ES6 and higher, also have this construct). The keyword used for this is “yield”. Yield can be called multiple times in the course of the operation of function. The result of that function will then be an iterator from which the successive arguments of yield can be pulled. So the method is programmed push-style, as values are pushed with yield. The result of the entire method however is an iterator which is pull-style. The disparity between push-style and pull-style is bridged by the compiler, that somehow keeps the state of the progressing algorithm between successive calls of yield, and activates the algorithm each time next() is called on the associated iterator.

Scala does not offer a yield keyword with this meaning (for the time being: Scala 2.12). However, there is a Scala construct with which we can come close to python-style generators. It is called Delimited Continuation and it is available in the language with the keywords “reset” and “shift“. In fact, Delimited Continuations as offered in Scala 2.11.6 is a very powerful construct with which much more can be done than just converting push-style generators into pull-style generators. It is so powerful and counter-intuitive on first sight, that it took me days to comprehend all aspects of it. Plenty of explanations of Scala Delimited Continuations can be found on the web. I will try to give a very concise introduction and turn then to the usage of this construct to convert a push-style into a pull-style generator.

Consider the following piece of pseudo code:

reset {
    {preceding code}
    shift { k(): (A => B) => : C }
    {trailing code}
}

In this code, all processing after the shift-expression, the remaining of the computation, is available in the shift-expression as the function k (“k” is a placeholder, it can be named whatever you want). The continuation function k() can be used in the shift block to do something with the result of invoking k(). The continuation function k() has a parameter. Its type is the syntactical type of the shift-expression. So this shift-expression can be part of a bigger expression. This bigger expression will be considered part of the “remaining of the computation”, and by supplying a parameter to the use of k() in the shift expression, the processing of the “remaining of the computation” in k() can be parameterized. A concrete example:

reset {
    val a = 2
    def f(x: Int): Int = x * x + 10
    val b = f( shift { k(): (Int => Int) => k(a) + 5 } )
    b * 3
}

The result of this construction is… 47. Not so easy to see when you are not familiar with continuations though. Everything after the first occurrence of the shift-expression will be made available in the continuation function k(). This includes the call of f() around the shift expression and the assignment of the result to val b. So k() can be written as

def k(x: Int) => { val b = f(x); b * 3 }

The result of the entire construct is now the last expression in the shift block: k(a) + 5. Knowing a and having explicit k() enables us to calculate:

k(a) + 5
substitute k() gives:
{ val b = f(a); b * 3 } + 5
substitute f() gives:
{ val b = a * a + 10; b * 3 } + 5
substitute a gives:
{ val b = 2 * 2 + 10; b * 3 } + 5
substitute b gives:
(2 * 2 + 10) * 3 + 5 = 47.

Examples like this one can be found in many explanations of Scala Delimited Continuations. This is straight forward execution broken up by the one time use of a continuation function. It has not much use besides providing nice puzzles for those who want to understand continuations. The practical use of continuations comes when one breaks up the execution of a complicated algorithm with iteration constructs like while-loops or recursion. So let’s turn our attention to a pull-type generator for unordered combinations without repetition.

class NonRepeatingCombContinuation[T](elems: List[T], genSize: Int) extends Iterable[List[T]] {
    private var hasNextVar = true
    private var state: (Unit => Unit) = null
    private var value: List[T] = Nil
    reset {
        def nonRepeatRec(elems: List[T], genSize: Int, partResult: List[T]): Unit @cpsParam[Unit, Unit] = {
            if (elems.size == genSize) provide(elems.reverse ::: partResult)
            else {
                if (!elems.isEmpty) {
                    nonRepeatRec(elems.tail, genSize, partResult)
                    if (genSize > 0) nonRepeatRec(elems.tail, genSize - 1, elems.head :: partResult)
                }
            }
        }
        if (genSize < 0) throw new IllegalArgumentException("Negative lengths not allowed in Perm.repeating...") if (genSize > elems.size) throw new IllegalArgumentException("Lengths over elems.size not allowed in Comb.nonRepeat...")
        nonRepeatRec(elems.reverse, genSize, Nil)
        hasNextVar = false
    }
    def provide(listT: List[T]): Unit @cpsParam[Unit, Unit] = {
        shift { k: (Unit => Unit) => { state = k; value = listT } }
    }
    override def iterator: Iterator[List[T]] = new Iterator[List[T]] {
        override def hasNext: Boolean = hasNextVar
        override def next(): List[T] = {
            val fix = value
            state()
            fix
        }
    }
}

In this piece of tested working Scala code with Delimited Continuations (I have seen quite a few examples on the web with Scala Delimited Continuations that didn’t work), one easily recognizes the original recursive push-generator function. Instead of the call to the callback, we now see a call to the “provide” function (“yield” would have been more like Python but “yield” has already a different meaning in Scala). The provide function contains the shift expression. The operation is straight forward:

The code in the reset block is executed as part of the construction of the class. Execution finally reaches a shift block via the call to provide(). In this shift block the “remaining of the computation” is not executed, but stored for later use in the variable state. The computed value that is parameter of provide() is stored in the variable value. Both these variables enable us to write the next() function of an iterator. In next() we first “fix” the value in value because the call of state() (the activation of the “remaining of the computation”) will generate a new value and overwrite the old that has yet to be handed out. After value has been safely stored in fix, the remaining of the computation, stored in state, is activated. This means continuation of the recursive algorithm until the shift block is encountered again via provide(), or the termination of the algorithm if all values to be generated have been done. After the termination of the continuation by the call of state(), the original “fixed” value is delivered by next(). Notice however that the next value has already been generated, and is waiting to be delivered in the variable value. So the strategy in this implementation is that the computation of combinations is executed up until the first combination is ready, before the first call of next(). The first call of next() computes the second combination and delivers the first. The second call of next() computes the third and delivers the second, and so on.

This strategy is necessary to be able to efficiently implement the other method of the iterator: hasNext(). The calls to both next() and hasNext() require the same computation to be performed: next() to determine the next value if there is one, and hasNext() to determine if there is a next value. The same computation will provide the next value and the information whether or not there is such a next value. The easiest way to do this efficiently is to do the computation in advance and store the results. The result for next() is stored in value, the result for hasNext() is stored in hasNextVar. The variable hasNextVar is initialized to true and is changed to false upon completion of the recursive algorithm (the last statement of the reset block sets hasNextVar to false).

It is easy to see this works by considering the case in which there is not a single value to be delivered and the case in which the last value of a non-zero length sequence has been delivered. The case in which there is not a single value is a hypothetical one for this particular algorithm, since there is always at least one unordered combination without repetition. Even when the underlying set is the empty set, there will be generated one zero-length combination. But imagine a recursive algorithm in the reset block that will never call provide(). This algorithm will run to completion before the first call to next() and hasNext(). That means that hasNextVar is set to false and the call to hasNext() delivers rightfully the value false. The call to next() will deliver the value value was initialized with, in this case Nil. This is irrelevant however, since next() is according to specs undefined whenever hasNext() is false. Now consider the case that the last value is about to be delivered by a call to next(). Recall that this value has already been computed and is stored in the variable value. After computation and storage of this value, the remaining of the computation is stored in state. This remaining of the computation will contain no more calls of provide, since we assumed the last value is has just been computed. Therefore the remaining of the computation will run the recursive algorithm to completion and execute the last statement of the reset block and set hasNextVar to false. This means all will go well: as long as the call to next() to deliver the last value has not occured, hasNextVar remains true. The call to next() delivers the last value (that was already computed and stored in variable value), and activates the last piece of remaining computation, that sets hasNextVar to false. So after delivering the last value, hasNext() will deliver false, as desired. It is easy to see that calling next() after hasNext() has become false will just deliver the last value again in this implementation. The previous call of next() did not encounter a provide() call and a shift block, so the variables value and state have not been overwritten with new values. Calling next() in this situation will just execute the “remaining of the computation” stored in state. hasNextVar will be assigned false again, and the same value value will be delivered again. No problem! Officially, next() is undefined as soon as hasNext() is false.

What is the relationship between the various generators discussed above and the ReactiveX framework? ReactiveX is: “An API for asynchronous programming with observable streams” (quote from reactivex.io, which should be a credible source). ReactiveX is about push-style processing. It is easy therefore to rewrite the four basic push-style generator functions for permutations and combinations into a ReactiveX Observable. An example will be given below. What has been said above about converting push-style generators into pull-style generators is another story. ReactiveX is about push-style processing. ReactiveX offers abundant and varied primitives to generate, convert and combine push-style generators (Observables). It is possible to convert an Observable into a pull-style generator, for instance with the methods toIterator and toIterable. However, these methods are blocking, which means that the result is made available only after the entire Observable has been consumed and completion is explicitly signalled. Obviously one has chosen the simplest implementation: generating everything in memory and providing an iterator that reads the values from memory. However, such an implementation will potentially suffer from an unacceptable memory footprint and from an unacceptable startup delay. So ReactiveX offers no cheap solution to the push-pull conversion problem! I have also tried the newest generation ReactiveX framework: Reactor 3 from the Reactor Project. This framework offers the “Flux”, an observable that supports “back-pressure”. The Flux is an observable, but can be effectively used as an iterator, as it offers a way to limit emissions to one at a time. However, to make this possible the Flux uses buffering to stash unconsumed emissions. There is some improvement since the RxJava 2 Observable: Flux is not blocking until completion is signaled. It can handle potentially infinite sequences. But what I am waiting for is a construction like the Python/ES6 yield, with which a programmatically generated sequence can be halted right in the generation process in case of back-pressure. Not buffering results that cannot yet be emitted but temporarily halting the generation process. Push-pull conversion is a non-trivial problem that requires intricate call-stack manipulation. It is impossible to solve this in a library if the language does not already has powerful primitives for it, like the Scala Limited Continuation. Of course Python and ES6 have the feature out of the box in the language with the yield construct.

Our nonRepeatingComb generator function as a ReactiveX Observable:

object ReactiveExperimenter extends App {
    val ob: Observable[List[String]] = Observable.apply((emitter: Subscriber[List[String]]) => {
        PermComb.nonRepeatingComb(List("A", "B", "C", "D", "E", "F", "G"), 3, emitter.onNext)
        emitter.onCompleted()
    })
    ob.subscribe(
        onNext => println("Value received: " + onNext),
        onError => println("Error occurred: " + onError.getStackTrace),
        () => println("Stream completed!")
    )
}

How does our pull-style generator with Delimited Continuations perform? I have compared performance of all variant algorithms for generating all unordered combinations of 13 elements without repetition from a set of 26. The elements were 26 length 1 strings “A”, “B”,…, “Z”. There are 10.400.600 such combinations. So we are looking at the speed of generating over ten million lists with 13 strings of length 1. We should be aware of the fact that the experimental setting is such that the garbage collector will not be triggered in the course of the algorithms. However, none of the algoritms will produce substantially more or substantially less garbage than the other ones, so the numbers will have relative significance.

  • Push-style generator: on average 842 milliseconds.
  • Pull-style generator algorithm with explicit callstack: on average 1825 milliseconds.
  • Pull-style generator algorithm with Delimited Continuations: on average 1664 milliseconds.

We see that the solution with Scala Delimited Continuations performs as good as, even a bit better, than the algorithm with explicit call stack. It should be noted that using the reset-shift constructs in Scala is extremely difficult. It took me days to comprehend all the implications of this concept, and each new experiment I did with it took substantial amounts of time to get it right. The type system of Scala will often protest and it is difficult to satisfy the compiler. In my view, Delimited Continuations are too difficult to use for the conversion of push-style into pull-style generators. A construct like the Python yield is preferable for this problem. It might be that this can be build with Scala Delimited Continutations since Scala is a highly extensible language, but I have my doubts. I doubt if you ever can get rid of the type annotations that Scala Delimited Continuations require for the transformation of reset-shift constructions. I have heard rumors that Delimited Continuations will be discontinued in the Scala language because it is too powerful and too difficult. The situation is comparable to the old fashioned goto. Goto is extremely powerful! But using it will ruin transparency and maintainability of your code, therefore we don’t want goto in our language, or at least strongly discourage usage of it.

Another interesting lesson from this experiment is that push-style generators are definitely faster than pull-style generators. If you are craving for performance, and this will occur more often than not in solving problems with combinatoric aspects, then you should go for the push-generators. This is conceptually a bit more difficult because of the involvement of callback functions, but it pays in terms of performance.

I have also considered generating combinations with standard sets {0, 1, 2,…, N-1} and mapping the generated combinations of natural numbers to some desired set. This works perfectly since the nature of the objects to be combined has no influence at all on the combinations to be generated. By choosing this approach, certain aspects of the algorithms become easier. The generating algorithms do not have to be generic, and instead of supplying a set of objects, one can supply a number: the number of elements in the set, which is sufficient to fix a set {0, 1, 2,…, N-1}. However, the generic approach in which sets (lists) with objects are supplied performs substantially better. Actually an algorithm that combines objects also combines numbers because what is manipulated is just pointers to objects. Manipulating pointers is in no way more difficult than manipulating natural numbers. Moreover, an algorithm that manipulates pointers does not need a mapping from integers to objects with every generated combination. It appears that an extra mapping with each generated combination will more than double the time to generate the required combination of objects.

How about push-style generators in Java? I have converted the Scala algoritm for unordered combinations without repetition to Java (8).

public class CombinationsUtil {

    public void nonRepeatingComb(LinkedList elems, int genSize, Predicate<LinkedList> callBack) {
        if (genSize < 0) throw new IllegalArgumentException("Negative lengths not allowed in nonRepeatingComb..."); if (genSize > elems.size())
            throw new IllegalArgumentException("Lengths over elems.size not allowed in nonRepeatingComb...");
        LinkedList workCopy = (LinkedList)elems.clone();
        Collections.reverse(workCopy);
        nonRepeatingCombRec(workCopy, genSize, callBack, new LinkedList());
    }

    private boolean nonRepeatingCombRec(LinkedList elems, int genSize, Predicate<LinkedList> callBack, LinkedList partResult) {
        boolean cont = true;
        if (elems.size() == genSize) {
            LinkedList workCopy = (LinkedList)elems.clone();
            Collections.reverse(workCopy)
            workCopy.addAll(partResult);
            cont = callBack.test(workCopy);
            return cont;
        }
        else {
            if (!elems.isEmpty()) {
                LinkedList elemsCopy = (LinkedList)elems.clone();
                T first = elemsCopy.removeFirst();
                cont = nonRepeatingCombRec(elemsCopy, genSize, callBack, partResult);
                if (genSize > 0 && cont) {
                    LinkedList partResultCopy = (LinkedList)partResult.clone();
                    partResultCopy.addFirst(first);
                    cont = nonRepeatingCombRec(elemsCopy, genSize - 1, callBack, partResultCopy);
                }
                return cont;
            }
            else return true;
        }
    }
}

this variant of the push-style generator continues as long as the callback delivers true (it stops at the first occurence of false from the callback). It is obvious that the Java version of the algorithm is a lot less elegant than the Scala version. Performance is also a lot worse.

  • Push-style generator Scala: on average 842 milliseconds.
  • Push-style generator Java: on average 3357 milliseconds.

Problem is that Java lacks a decent immutable singly linked list. There is at least nothing like it in the java.util package. Java’s LinkedList is doubly linked and mutable. This means there is no fast “tail” operation with which one can “remove” the first element of the list without throwing away the original list. In the Scala version of the algorithm, the “tail” operator is used extensively. To mimic this operator in Java one has to make a copy of the original list before removing the first element. Same holds for the situation in which an element has to be added to the front of the list.

I have made a simple singly linked list implementation in Java, and repeated the performance test on a variant of the algorithm, using this simple list implementation. The results are staggering:

  • Push-style generator Java with LinkedList: on average 3357 milliseconds.
  • Push-style generator Java with home made singly linked list: on average 455 milliseconds.

This is amazing! With a simple list implementation performance jumps by almost a factor 10. I have devoted a separate article to the Java immutable singly linked list container implementation, and the Java variants of the generator function. It’s clear to me that Java needs a decent immutable singly linked list in the java.util package. At least if Java wants to be taken serious as a language that supports functional programming. The lessons: when performance is really important: use Java and not Scala. Write your own generic containers, if a suitable one is not in the standard library. One would think that standard library containers are always faster than home made ones. Not true! I got fastest results with a home made generic immutable singly linked list. This was considerably faster than the Scala solution with the standard Scala immutable singly linked list (at least Scala offers one, but it is not nearly as fast as a home made variant with Java).