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.