使用假设生成具有自定义值限制的列表列表

Question

故事：

目前，我有一个待测函数需要一个 整数列表列表，其规则如下：

子列表的数量（我们称之为 N）可以是 1 到 50
子列表中值的数量对于所有子列表（矩形形式）都是相同的，应该 >= 0 且 <= 5
子列表中的值不能大于或等于子列表的总数。换句话说，子列表中的每个值都是一个整数 >= 0 且 < N

有效输入示例：

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

无效输入示例：

[[2]]  # 2 is more than N=1 (total number of sublists)
[[0, 1], [2, 0]]  # 2 is equal to N=2 (total number of sublists)

我正在尝试使用 属性-based-testing 来处理它，并使用 hypothesis library 生成不同的有效输入并尝试绕过我的头lists() 和 integers()，但无法使其工作：

条件 #1 很容易通过 lists() 和 min_size 以及 max_size 参数来实现
条件 #2 包含在 Chaining strategies together
条件 #3 是我正在努力解决的问题 - 因为，如果我们使用上面示例中的 rectangle_lists，我们没有对 "parent" 长度的引用列表里面 integers()

问题：

如何限制子列表中的整数值小于子列表的总数？

我的一些尝试：

from hypothesis import given
from hypothesis.strategies import lists, integers

@given(lists(lists(integers(min_value=0, max_value=5), min_size=1, max_size=5), min_size=1, max_size=50))
def test(l):
    # ...

这个远远不能满足要求 - 列表不是严格的矩形形式，生成的整数值可以超过列表的生成大小。

from hypothesis import given
from hypothesis.strategies import lists, integers

@given(integers(min_value=0, max_value=5).flatmap(lambda n: lists(lists(integers(min_value=1, max_value=5), min_size=n, max_size=n), min_size=1, max_size=50)))
def test(l):
    # ...

此处，#1 和#2 要求得到满足，但整数值可以大于列表的大小 - 要求#3 未得到满足。

Answer 1

有一个很好的通用技术，在尝试解决像这样的棘手约束时通常很有用：尝试构建一些看起来有点像你想要的但不满足所有约束的东西，然后用一个函数组合它修改它（例如，通过丢弃坏位或修补不太有效的位）以使其满足约束。

对于您的情况，您可以执行以下操作：

from hypothesis.strategies import builds, lists, integers

def prune_list(ls):
    n = len(ls)
    return [
       [i for i in sublist if i < n][:5]
       for sublist in ls
    ]

limited_list_strategy = builds(
   prune_list,
   lists(lists(integers(0, 49), average_size=5), max_size=50, min_size=1)
)

在此我们：

生成一个看起来大致正确的列表（它是一个整数列表，整数与所有可能可能有效的索引在同一范围内）。
从子列表中删除所有无效索引
截断任何仍包含 5 个以上元素的子列表

结果应满足您需要的所有三个条件。

average_size 参数不是绝对必要的，但在对此进行试验时我发现它有点太容易产生空的子列表，否则。

预计到达时间：抱歉。我刚刚意识到我误读了您的一个条件 - 这实际上并没有完全按照您的意愿行事，因为它不能确保每个列表的长度相同。这是一种修改它来修复它的方法（它变得有点复杂，所以我改用复合而不是构建）：

from hypothesis.strategies import composite, lists, integers, permutations


@composite
def limisted_lists(draw):
    ls = draw(
        lists(lists(integers(0, 49), average_size=5), max_size=50, min_size=1)
    )
    filler = draw(permutations(range(50)))
    sublist_length = draw(integers(0, 5))

    n = len(ls)
    pruned = [
       [i for i in sublist if i < n][:sublist_length]
       for sublist in ls
    ]

    for sublist in pruned:
        for i in filler:
            if len(sublist) == sublist_length:
               break
            elif i < n:
               sublist.append(i)
    return pruned

我们的想法是，我们生成一个 "filler" 列表，该列表提供子列表的默认外观（因此它们会朝着彼此更相似的方向收缩），然后绘制长度要修剪以获得一致性的子列表。

我承认这已经相当复杂了。您可能想使用 RecursivelyIronic 的基于平面图的版本。我更喜欢这个的主要原因是它会收缩得更好，所以你会从中得到更好的例子。

Answer 2

您也可以使用 flatmap 执行此操作，尽管这有点扭曲。

from hypothesis import strategies as st
from hypothesis import given, settings

number_of_lists = st.integers(min_value=1, max_value=50)
list_lengths = st.integers(min_value=0, max_value=5)

def build_strategy(number_and_length):
    number, length = number_and_length
    list_elements = st.integers(min_value=0, max_value=number - 1)
    return st.lists(
        st.lists(list_elements, min_size=length, max_size=length),
        min_size=number, max_size=number)

mystrategy = st.tuples(number_of_lists, list_lengths).flatmap(build_strategy)

@settings(max_examples=5000)
@given(mystrategy)
def test_constraints(list_of_lists):
    N = len(list_of_lists)

    # condition 1
    assert 1 <= N <= 50

    # Condition 2
    [length] = set(map(len, list_of_lists))
    assert 0 <= length <= 5

    # Condition 3
    assert all((0 <= element < N) for lst in list_of_lists for element in lst)

正如 David 所提到的，这确实会产生大量空列表，因此需要进行一些平均大小调整。

>>> mystrategy.example()
[[24, 6, 4, 19], [26, 9, 15, 15], [1, 2, 25, 4], [12, 8, 18, 19], [12, 15, 2, 31], [3, 8, 17, 2], [5, 1, 1, 5], [7, 1, 16, 8], [9, 9, 6, 4], [22, 24, 28, 16], [18, 11, 20, 21], [16, 23, 30, 5], [13, 1, 16, 16], [24, 23, 16, 32], [13, 30, 10, 1], [7, 5, 14, 31], [31, 15, 23, 18], [3, 0, 13, 9], [32, 26, 22, 23], [4, 11, 20, 10], [6, 15, 32, 22], [32, 19, 1, 31], [20, 28, 4, 21], [18, 29, 0, 8], [6, 9, 24, 3], [20, 17, 31, 8], [6, 12, 8, 22], [32, 22, 9, 4], [16, 27, 29, 9], [21, 15, 30, 5], [19, 10, 20, 21], [31, 13, 0, 21], [16, 9, 8, 29]]
>>> mystrategy.example()
[[28, 18], [17, 25], [26, 27], [20, 6], [15, 10], [1, 21], [23, 15], [7, 5], [9, 3], [8, 3], [3, 4], [19, 29], [18, 11], [6, 6], [8, 19], [14, 7], [25, 3], [26, 11], [24, 20], [22, 2], [19, 12], [19, 27], [13, 20], [16, 5], [6, 2], [4, 18], [10, 2], [26, 16], [24, 24], [11, 26]]
>>> mystrategy.example()
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
>>> mystrategy.example()
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
>>> mystrategy.example()
[[6, 8, 22, 21, 22], [3, 0, 24, 5, 18], [16, 17, 25, 16, 11], [2, 12, 0, 3, 15], [0, 12, 12, 12, 14], [11, 20, 6, 6, 23], [5, 19, 2, 0, 12], [16, 0, 1, 24, 10], [2, 13, 21, 19, 15], [2, 14, 27, 6, 7], [22, 25, 18, 24, 9], [26, 21, 15, 18, 17], [7, 11, 22, 17, 21], [3, 11, 3, 20, 16], [22, 13, 18, 21, 11], [4, 27, 21, 20, 25], [4, 1, 13, 5, 13], [16, 19, 6, 6, 25], [19, 10, 14, 12, 14], [18, 13, 13, 16, 3], [12, 7, 26, 26, 12], [25, 21, 12, 23, 22], [11, 4, 24, 5, 27], [25, 10, 10, 26, 27], [8, 25, 20, 6, 23], [8, 0, 12, 26, 14], [7, 11, 6, 27, 26], [6, 24, 22, 23, 19]]

Answer 3

很晚了，但为了后代：最简单的解决方案是选择维度，然后从元素策略开始构建。

from hypothesis.strategies import composite, integers, lists

@composite
def complicated_rectangles(draw, max_N):
    list_len = draw(integers(1, max_N))
    sublist_len = draw(integers(0, 5))
    element_strat = integers(0, min(list_len, 5))
    sublist_strat = lists(
        element_strat, min_size=sublist_len, max_size=sublist_len)
    return draw(lists(
        sublist_strat, min_size=list_len, max_size=list_len))

使用假设生成具有自定义值限制的列表列表

Generating list of lists with custom value limitations with Hypothesis

python

testing

unit-testing

property-based-testing

python-hypothesis