random.sample() does not properly check 'counts' parameter for negative entries, resulting in a flawed binary search.

[boniest]

Bug report

Bug description:

the sample method in Random takes a counts parameter which is accumulated in the algorithm to cum_counts.

the total of counts (ie. the final element of cum_counts) is checked for non-negativity, but the individual elements of counts are not.

this causes a bug because the accumulated cum_counts is NOT strictly non-decreasing BUT a bisect (ie. binary search) is performed on cum_counts.

this call to Random.sample() always results in [3, 3] because a bisect using either 0 and 1 over cum_counts results in 3.

import random
result = random.sample([0,1,2,3,4], counts=[4,-6,-1,6,-1], k=2)
print(result) # always [3, 3]

CPython versions tested on:

3.13

Operating systems tested on:

Windows

[pochmann3]

That parameter is for counts. Not for arbitrary numbers. It's the caller's bug. See Garbage in, garbage out and a similar issue about random.choices.

[boniest]

okay. makes sense.

not that it matters but i supposed it was a bug because the total is checked but not elements.