I was working on fixing a bug in Aloha when I came across a usage of Scala’s combinations function in the SeqLike trait. I’d never used it before and was a little disappointed when I found that:

If there is more than one way to generate the same subsequence, only one will be returned.

What I thought (and hoped) it did was create the list of k-subsequences. Nope. So I figured I’d write something that actually computes what I wanted. I wanted four things in the implementation:

1. Accuracy
2. Speed

Accuracy will be discussed below the code. Click here for that discussion. Speed is also an obvious concern. To ensure iteration is fast, I used an adaptation of Nils Pipenbrinck’s response to the stack overflow post Creating multiple numbers with certain number of bits set. The algorithm employs bit hacks and takes 5 64-bit long operations to find a the next value and k masking operations to build the k-subsequence. So the total runtime is $O\left( k \right)$. The total auxiliary space is 2 64-bit integers and one AtomicLong for a total of $O\left( 1 \right)$ auxiliary space.

The last concern is thread-safety. While the algorithm produces iterators that are thread-safe, I still want this to be fast. So I use AtomicLong and CAS operations to avoid blocking.

## Accuracy

To test accuracy, we want to make sure that the number of k-subsequences is $\left( \begin{matrix} n \\ k \end{matrix} \right)$, which is equivalent to the number k-element subsets of of n-element set. See the wikipedia article on the binomial coefficient for why this is true. The following code calculates the binomial coefficients:

Then we can test that the proper number of k-subsequences are outputted.

## Conclusion

“Well, there you have it.” A fast, thread-safe, memory efficient k-subsequence iterator. Enjoy!