Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Iterator (lazy) style class to compute all the combinations of any number of given lists.
/*
* 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()
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment