# Evenly spaced sample

While building a trivia application for 2020’s Video Conferenced Christmas, I had need of a function that would provide an evenly spaced sample from a given list.

I considered random.choices, but the results aren’t evenly spaced. I considered numpy.linspace, but the conversion of its floats to integer list indices results in odd edge-cases that can bunch up values.

In need of a holiday puzzle, I sat down to take care of it myself. If you’re interested in the same sort of thing, read only the docstring and try to build something that achieves the same thing yourself!

``````import random

def evenly_spaced_sample(lst, total):
"""Return evenly spaced out elements of the given list

## Deterministic outcomes

>>> evenly_spaced_sample([0,1, 2, 3,4,5,6, 7, 8,9], 2)
[2, 7]

>>> evenly_spaced_sample([0, 1, 2,3, 4, 5], 2)
[1, 4]

>>> evenly_spaced_sample([0,1,2], 1)


>>> evenly_spaced_sample(['a', 'b'], 2)
['a', 'b']

>>> evenly_spaced_sample(['a', 'b', 'c'], 2)
['a', 'c']

## Non-deterministic outcomes

>>> sorted(set(
...     tuple(evenly_spaced_sample([0,1,2,3,4,5,6,7], 4))
...     for x in range(100)
... ))
[(0, 2, 4, 6), (1, 3, 5, 7)]

>>> sorted(set(
...     tuple(evenly_spaced_sample([0, 1, 2,3, 4,5, 6,7, 8, 9], 3))
...     for x in range(100)
... ))
[(1, 4, 8), (1, 5, 8)]

>>> sorted(set(
...     tuple(evenly_spaced_sample(['a', 'b'], 1))
...     for x in range(100)
... ))
[('a',), ('b',)]
"""

# Handle the edge cases
len_lst = len(lst)
if len_lst == total:  # Requesting all items
return lst
elif total == 0:  # Requesting no items
return []
elif total < 0 or len_lst < total:  # Requesting too many items
raise ValueError("Sample larger than population or is negative")

"""
Imagine a list like [0,1,2,3,4,5,6,7,8,9] and we want 3 evenly spaced
items. The list length (10) divided by the number of items (3) gives
us 3.3~, so we know our evenly spaced items must be at least 3 apart
from one another. There's also one more space we need to assign to one
of the spaces.
"""

# Determine the space between items and how many gaps of each size we need
gap_min = int(len_lst / total)
gap_max = gap_min + 1
gap_max_count = len_lst - gap_min * total
gap_min_count = total - gap_max_count

# Generate a list of offsets, ensuring that the tail has a min gap
offsets = [gap_min] * (gap_min_count - 1) + [gap_max] * gap_max_count
random.shuffle(offsets)
offsets.append(gap_min)

"""
Next, we need to make sure that we're not returning [0,3,7] as that's
what you might call "left aligned". We want our evenly spaced sample
to be somewhat centered. We can do this by shifting our starting index
over by half of the last offset (considering the head and the tail to
be one "space" between items, as though the given list were a ring.
"""

# The starting index is half the last offset, adjusted if it's not an int
shift = (offsets[-1] - 1) / 2
index = int(shift)
if not shift.is_integer() and shift - index < random.random():
index += 1

# Compose and return the response list
response = []
for offset in offsets:
response.append(lst[index])
index += offset
return response

if __name__ == "__main__":
import doctest
doctest.testmod()
``````

Looking around after writing this, I come across some similar problems (e.g. StackOverflow’s Random list of numbers in a range keeping with a minimum distance, but nothing quite like what I’m trying to achieve. I have no doubt someone out there has written something similar, but sometimes it’s difficult to bring these things to the surface.

Worth noting that the more complex the problem, the more time you’d want to spend on investigating prior work instead of just building it from scratch.