Iterator (lazy) style class to compute all the combinations of any number of given lists.

ListCombinations.groovy

/*
 * Author: Bahman Movaqar <Bahman AT BahmanM.com>
 * Copyright (c) Bahman Movaqar
 * This file is released under public domain license.
 */
///// Tests below the main class

import groovy.transform.PackageScope

/**
 * Lazy (iterator) style combinations of multiple lists. It is important to note
 * that the order of the iteration is not guaranteed and might vary each time
 * the class is initialised.
 *
 * @param < T > type of elements of the lists
 */
class ListCombinations<T> implements Iterator<List<T>> {

    /** input lists */
    final List<List<T>> input = []
    /** index value limit for each list in input */
    final private List<Integer> indexLimits = []
    /** current index values into lists of input */
    private List<Integer> indexCurrent

    /**
     * Creates a new instance making a copy of input lists.
     *
     * @param lists lists to calculate the combinations of
     */
    ListCombinations(List<T>... lists) {
        assert lists?.every { !it?.empty }
        lists.each {
            input << (it.clone() as List<T>)
            indexLimits << it.size() - 1
        }
        indexCurrent = []
    }

    /**
     * Fobidden.
     */
    protected ListCombinations() {
        throw new UnsupportedOperationException()
    }

    /**
     * Checks if there is another combination left.
     *
     * @return true if there is another combination, false otherwise
     */
    @Override
    boolean hasNext() {
        indexCurrent.empty ||
        [indexLimits, indexCurrent].transpose().any { l, c ->
            l > c
        }
    }

    /**
     * Calculates the next combination of the input lists.<br/>
     * NOTE: The order of the combinations is not guaranteed.
     *
     * @return the next combination
     */
    @Override
    List<T> next() {
        if (!hasNext())
            throw new NoSuchElementException()
        indexCurrent = incIndexCurrent(indexLimits, indexCurrent)
        [0..input.size(), indexCurrent].transpose().collect { i1, i2 ->
            input[i1][i2] as T
        }
    }

    /**
     * Increments 'indexCurrent' by 1. The "update" is practically an
     * "add with carry" operation, with carry set to 1 at the beginning.
     *
     * @return copy of currentIndex, incremented by 1
     */
    @PackageScope static
    List<Integer> incIndexCurrent(
        List<Integer> limits, List<Integer> current
    ) {
        if (current.empty)
            return [0] * limits.size() - 1
        def result = (current.clone()) as List
        def carry = 1
        for (Integer i in 0..result.size()-1) {
            result[i] = result[i] + carry
            if (result[i] > limits[i]) {
                // overflow
                result[i] = 0
                carry = 1
            } else {
                // no overflow
                carry = 0
            }
        }
        result
    }

    /**
     * Forbidden.
     *
     * @throws UnsupportedOperationException
     */
    @Override
    void remove() {
        throw new UnsupportedOperationException()
    }

}

///////////////////////////////////////////////
///////////////////////////////////////////////
import org.junit.Test
import static groovy.test.GroovyAssert.*
import static ListCombinations.incIndexCurrent

class ListCombinationsTest {

    @Test
    void incIndexCurrent() {
        def limits1 = [1,1]
        assert incIndexCurrent(limits1, [0,0]) == [1,0]
        assert incIndexCurrent(limits1, [1,0]) == [0,1]
        assert incIndexCurrent(limits1, [0,1]) == [1,1]

        def limits2 = [1,1,1]
        assert incIndexCurrent(limits2, [0,0,0]) == [1,0,0]
        assert incIndexCurrent(limits2, [1,0,0]) == [0,1,0]
        assert incIndexCurrent(limits2, [0,1,0]) == [1,1,0]
        assert incIndexCurrent(limits2, [1,1,0]) == [0,0,1]
        assert incIndexCurrent(limits2, [0,0,1]) == [1,0,1]
        assert incIndexCurrent(limits2, [1,0,1]) == [0,1,1]
        assert incIndexCurrent(limits2, [0,1,1]) == [1,1,1]
    }

    @Test
    void next() {
        def l1 = [0,1]
        def lc1 = new ListCombinations(l1,l1,l1)
        assert lc1.next() == [0,0,0]
        assert lc1.next() == [1,0,0]
        assert lc1.next() == [0,1,0]
        assert lc1.next() == [1,1,0]
        assert lc1.next() == [0,0,1]
        assert lc1.next() == [1,0,1]
        assert lc1.next() == [0,1,1]
        assert lc1.next() == [1,1,1]

        def l2 = ['a', 'b', 'c']
        def l3 = [10.01, 11.22]
        def l4 = [true, false]
        def lc2 = new ListCombinations(l2,l3,l4)
        assert lc2.next() == ['a', 10.01, true]
        10.times { lc2.next() }
        assert lc2.next() == ['c', 11.22, false]
        shouldFail(NoSuchElementException, {
            lc2.next()
        })
    }

    @Test
    void createDeepCopy() {
        def l1 = [0,1]
        def lc1 = new ListCombinations(l1,l1,l1)
        lc1.next()
        l1[0] = 20
        l1[1] = 30
        assert lc1.next() == [1,0,0]
    }

    @Test
    void hasNext() {
        def l1 = [0,1]
        def lc = new ListCombinations(l1,l1,l1)
        (0..6).each { lc.next() }
        assert lc.hasNext()
        lc.next()
        assert !lc.hasNext()
    }

}