Thursday, November 19, 2015

Computing n-tuple Combinations of a Set - Java

Introduction

I recently ran into a problem while building the type compiler for my proprietary scripting language.  It seemed like a braindead problem I should have remembered from my high-school days of coding.  After reviewing a few recursive and somewhat clumsy examples on the Internet, and also after decidedly turning down Guava (In interest of compactness, external dependencies on my compiler are kept at a minimum), I decided to attack the problem on my own.

Problem

Calculate the complete list of n-tuple combinations of elements in a set of arbitrary type.  For example, computing the triple (3-tuple) list of combinations of the following set should satisfy the following:

Input: [1, 2, 3, 4, 5]
Output: [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

Features

I came up with a solution that boasts the following features:

  1. Iterable (no memory consumption)
  2. Non-recursive (no stack juggling)
  3. n-tuple combinations only (as opposed to permutations)

Code

Here's the code:
package com.extollit.collect;

import java.text.MessageFormat;
import java.util.*;

public class CombinationsIterable<T> implements Iterable<List<T>> {
    private final List<T> delegate;
    private final int rank;

    /**
     * Create an iterable list over the specified list that returns an iterator for iterating over
     * all the n-tuple combinations in the list (n-tuple specified by the rank parameter).
     *
     * @param delegate The list to compute n-tuple sub-set combinations from
     * @param rank The size of the combination tuple, must be > 0 and <= delegate size
     */
    public CombinationsIterable(List<T> delegate, int rank) {
        this.delegate = delegate;
        if (rank > delegate.size() || rank <= 0)
            throw new IllegalArgumentException(
                MessageFormat.format("Combination tuple size (rank) must be less than or equal to the delegate list size and greater than zero, but {0} <= 0 | > {1}", rank, delegate.size())
            );

        this.rank = rank;
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new ComboIter();
    }

    private class ComboIter implements Iterator<List<T>> {
        private final ArrayList<T> workspace = new ArrayList<T>(rank);
        private final int [] indexStack;
        private final int spanSize;

        private int stackPointer;
        private List<T> current = null;

        private ComboIter() {
            indexStack = new int[rank];
            stackPointer = 0;
            indexStack[0] = -1;
            spanSize = delegate.size() - indexStack.length;
            for (int c = 0; c < indexStack.length; ++c)
                workspace.add(c, null);
        }

        private List<T> findNext() {
            while (stackPointer >= 0 && ++indexStack[stackPointer] > spanSize + stackPointer) {
                stackPointer--;
            }

            if (stackPointer >= 0) {
                this.workspace.set(stackPointer, delegate.get(indexStack[stackPointer]));
                for (int c = stackPointer + 1; c < indexStack.length; ++c) {
                    indexStack[c] = indexStack[c - 1] + 1;
                    ++stackPointer;
                    this.workspace.set(c, delegate.get(indexStack[c]));
                }
                return this.workspace;
            } else
                return null;
        }

        @Override
        public boolean hasNext() {
            return acquireCurrent() != null;
        }

        @Override
        public List<T> next() {
            List<T> current = acquireCurrent();

            if (current != null) {
                current = new ArrayList<T>(current);
                this.current = findNext();
            }

            return current;
        }

        private List<T> acquireCurrent() {
            if (this.current == null)
                this.current = findNext();
            return this.current;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException(
                "Combinations iterator does not support removal of combinations because it's functional mapping to the underlying collection is non-injective"
            );
        }
    }
}

It passes a few of my tests, please notify me of any errors.