Strategy for subsequences/slices of given sequence (sub-lists/sub-tuples/sub-strings/etc.)

user_5997596 0
Viewed 97

How can I write a strategy for subsequences of given sequence?

For example given a list

elements = list(range(5))

I want a strategy

sub_elements = *strategy*(elements)

which generates

[]
[0]
[0, 2]
[1, 3, 4]
[0, 1, 2, 3, 4]

simple approach with combination of strategies.lists & strategies.sampled_from like

>>> from hypothesis import strategies
>>> strategies.lists(strategies.sampled_from(elements))

won't work because it doesn't take into account original elements count.

python-hypothesis python
1 Answers

The main idea is to use strategies.slices and then select items based on them

from collections import abc
from typing import TypeVar

from hypothesis import strategies
from hypothesis.strategies import SearchStrategy

Sequence = TypeVar('Sequence', bound=abc.Sequence)


def subsequences(sequence: Sequence) -> SearchStrategy[Sequence]:
    return strategies.builds(sequence.__getitem__,
                             strategies.slices(max(len(sequence), 1)))

it's pretty short, straightforward and should work for any sequences that support slicing like lists, tuples and strings (even for ranges, which is great IMO).

Example:

>>> elements = list(range(5))
>>> sub_elements = subsequences(elements)
[1, 3]
>>> sub_elements.example()
[4]
>>> sub_elements.example()
[0, 2, 4]

The only problem with that approach that we can't create all possible subsequences (like [0, 1, 4] for elements from OP).

It can be solved with strategies.permutations like

from operator import getitem
from typing import (List,
                    Sequence,
                    TypeVar)

from hypothesis import strategies
from hypothesis.strategies import SearchStrategy

Element = TypeVar('Element')


def sub_lists(sequence: Sequence[Element]) -> SearchStrategy[List[Element]]:
    return strategies.builds(getitem,
                             strategies.permutations(sequence),
                             strategies.slices(max(len(sequence), 1)))

but we lose original sequence type.

user_59975960
Related