Rockybilly Rockybilly - 4 years ago 117
Python Question

How to select distinct random points in grid

I have a 2D list, I need to select

n
distinct random points (x, y coordinates) from this 2D list. Let me first write what occured to me when I tried to solve the problem.

Let's say the grid is
300 x 400
.


  • Do cartesian product
    300 x 400
    get a list of
    120000
    elements, than use
    random.choice
    (Slow for large grids)

  • Keep the selected points in a set, randomize again in a while loop if a duplicate point is produced. (Very slow and unpredictable if n is large)



I searched some similar questions in SO, none of them address the problem directly. I did found This question, though the users answer the problem, they do not offer a Python solution, which we may produce here in this question. Maybe usage of appropriate data structures in Python standard library can be suggested if not code itself.

Answer Source

Use random.sample to sample without replacement from a range -- there's a fast special case for range objects. divmod(i, h) is the lexicographic mapping from i in the 1D range with w * h elements to (x, y) in the 2D grid.

Python 3:

import random
def samplegrid(w, h, n):
    return [divmod(i, h) for i in random.sample(range(w * h), n)]

Python 2:

import random
def samplegrid(w, h, n):
    return [divmod(i, h) for i in random.sample(xrange(w * h), n)]
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download