Generating list of lists with custom value limitations with Hypothesis
<p><strong>The Story:</strong></p>

<p>Currently, I have a function-under-test that expects a <em>list of lists of integers</em> with the following rules:</p>

<ol>
<li>number of sublists (let's call it <code>N</code>) can be from 1 to 50</li>
<li>number of values inside sublists is the same for all sublists (rectangular form) and should be >= 0 and &lt;= 5</li>
<li>values inside sublists cannot be more than or equal to the total number of sublists. In other words, each value inside a sublist is an integer >= 0 and &lt; <code>N</code></li>
</ol>

<p>Sample valid inputs:</p>

<pre><code>[[0]]
[[2, 1], [2, 0], [3, 1], [1, 0]]
[[1], [0]]
</code></pre>

<p>Sample invalid inputs:</p>

<pre><code>[[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)
</code></pre>

<p>I'm trying to approach it with <em>property-based-testing</em> and generate different valid inputs with <a href="http://hypothesis.readthedocs.io/en/latest/index.html"><code>hypothesis</code> library</a> and trying to wrap my head around <code>lists()</code> and <code>integers()</code>, but cannot make it work:</p>

<ul>
<li>the condition #1 is easy to approach with <code>lists()</code> and <code>min_size</code> and <code>max_size</code> arguments</li>
<li>the condition #2 is covered under <a href="http://hypothesis.readthedocs.io/en/latest/data.html#chaining-strategies-together"><code>Chaining strategies together</code></a></li>
<li>the condition #3 is what I'm struggling with - cause, if we use the <code>rectangle_lists</code> from the above example, we don't have a reference to the length of the "parent" list inside <code>integers()</code> </li>
</ul>

<p><strong>The Question:</strong></p>

<p>How can I limit the integer values inside sublists to be less than the total number of sublists?</p>

<hr>

<p>Some of my attempts:</p>

<pre><code>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):
    # ...
</code></pre>

<p>This one was very far from meeting the requirements - list is not strictly of a rectangular form and generated integer values can go over the generated size of the list.</p>

<pre><code>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):
    # ...
</code></pre>

<p>Here, the #1 and #2 are requirements were being met, but the integer values can go larger than the size of the list - requirement #3 is not met.</p>

<p>You can also do this with <code>flatmap</code>, though it's a bit of a contortion.</p>

<pre><code>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 &lt;= N &lt;= 50

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

    # Condition 3
    assert all((0 &lt;= element &lt; N) for lst in list_of_lists for element in lst)
</code></pre>

<p>As David mentioned, this does tend to produce a lot of empty lists, so some average size tuning would be required.</p>

<pre><code>&gt;&gt;&gt; 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]]
&gt;&gt;&gt; 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]]
&gt;&gt;&gt; mystrategy.example()
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
&gt;&gt;&gt; mystrategy.example()
[[], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
&gt;&gt;&gt; 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]]
</code></pre>

python unit-testing testing property-based-testing python-hypothesis