Generate a random list based on limited items with spock-genesis

Tsimon Dorakh 0
Viewed 58

I use spock-genesis and would like to have an infinite lists generator parametrized with a list of values. A generated item should be a list that contains at most the list of parametrized values in random order.

Some invariants are:

def 'list generator'() {
    expect:
    xs.size() <= 3
    xs.findAll({x -> x == 1}).size() <= 1
    xs.findAll({x -> x == 2}).size() <= 1
    xs.findAll({x -> x == 3}).size() <= 1

    where:
    xs << listGen([1, 2, 3])
}

I'm about to write own Generator implementation but there is chance I overthink something and it's possible to compose such generator with already existing spock-genesis units.

spock unit-testing groovy
3 Answers

Try this

List listGen(List list) {
    list.subsequences()
            .collect { it.permutations() }
            .inject([[]]) { result, subseq -> result + subseq }
}

The result of listGen([1, 2, 3]) will be:

[[], [1], [1, 2, 3], [3, 2, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [2], [3, 2], [2, 3], [2, 1], [1, 2], [3], [1, 3], [3, 1]]

Your test passes with this implementation.

UPD: As per the OP clarifications below in the comments, they expect the permutations to be random, so here is the line of code that will do that using spock-genesis any:

where:
xs << Gen.any(listGen([1, 2, 3])).take(42).collect() // I assume 42 here should be random as well then
Dmitry Khamitov0

I'm not quite sure what you want, is just a list of every possible permutation of the list [1,2,3]? If so then this should be enough.

[1, 2, 3].permutations()
Leonard Brünings0

With @Dmitry Khamitov help I've come up with spock-genesis generator

package spock.genesis.generators.composites

import groovy.transform.CompileStatic
import spock.genesis.generators.Generator
import spock.genesis.generators.UnmodifiableIterator
import spock.genesis.generators.values.RandomElementGenerator

/** A lazy infinite {@code Generator} that returns a random subset of elements from a source Collection
 * @warning O(n!) time complexity. Starts being too expensive with lists 10+ elements
 * @param < E >     the generated type
 */
@CompileStatic
class ListSubsetGenerator<E> extends Generator<List<E>> {
    final RandomElementGenerator<List<E>> valueSource

    ListSubsetGenerator(Collection<E> source) {
        this.valueSource = new RandomElementGenerator<>(getListsSource(source))
    }

    private List<List<E>> getListsSource(Collection<E> source) {
        source.toList().subsequences()
            .collect { it.permutations() }
            .inject([[]]) { result, subseq ->
                result.addAll(subseq)
                result
            } as List<List<E>>
    }

    @Override
    UnmodifiableIterator<List<E>> iterator() {
        new UnmodifiableIterator<List<E>>() {
            private final Iterator<List<E>> source = valueSource.iterator()

            @Override
            boolean hasNext() {
                source.hasNext()
            }

            @Override
            List<E> next() {
                source.next()
            }
        }
    }

    @Override
    Generator<List<E>> seed(Long seed) {
        super.seed(seed)
        valueSource.seed(seed)
        this
    }
}

Here are some tests:

class ListSubsetGeneratorTest extends Specification {
    @Iterations(100)
    def 'test invariants'() {
        expect:
        xs.size() <= 3
        xs.findAll({x -> x == 1}).size() <= 1
        xs.findAll({x -> x == 2}).size() <= 1
        xs.findAll({x -> x == 3}).size() <= 1
        xs.every { [1, 2, 3].contains(it) }

        where:
        xs << new ListSubsetGenerator([1, 2, 3])
    }

    def 'setting seed produces the same sequences for different generators'() {
        given:
        def elements = ['a', 'b', 'c', 'd']
        def xs = new ListSubsetGenerator(elements).seed(seed).take(100).realized
        def ys = new ListSubsetGenerator(elements).seed(seed).take(100).realized

        expect:
        xs == ys

        where:
        seed << [Long.MIN_VALUE, 100, Long.MAX_VALUE]
    }
}
Tsimon Dorakh0
Related