Generating random, non-repeating points on the plane

Question

The problem is to generate random points on the plane that are unique (i.e. no repetition of a point). The following won't work because of repetition:

In[86]:= RandomInteger[5, {3, 2}]
Out[86]= {{1, 3}, {3, 5}, {1, 3}}

So RandomSample may be the answer. But something like the following also repeats:

In[94]:= Table[RandomSample[Range[5], 2], {3}]
Out[94]= {{3, 4}, {4, 5}, {3, 4}}

Is there a clever solution to this?

Answer 1

Better is

RandomSample[Tuples[Range[5], 2], 3]

Your formula may generate the same point two-times or more

(try, for a counterexample

Table[RandomSample[Range[2], 2], {3}]

)

Answer 2

Another approach...if you want 10 points in a 3D space, with no repeats of a coordinate in any dimension...

dim = 3;
numPts = 10;
Transpose@(Ordering /@ Ordering /@ RandomReal[1, {dim, numPts}])

$ \begin{array}{ccc} 8 & 6 & 4 \\ 7 & 5 & 8 \\ 2 & 4 & 1 \\ 5 & 8 & 5 \\ 9 & 3 & 2 \\ 10 & 7 & 9 \\ 1 & 2 & 10 \\ 4 & 1 & 7 \\ 6 & 9 & 6 \\ 3 & 10 & 3 \\ \end{array} $

Data sets in this form (each column is a permutation of Range[numPts]) have a bunch of interesting combinatorial properties. What is fascinating is to take the transform and apply it to random data that is distributed in unique ways, such as points on a simplex, hypersphere, etc.

Expanding a wee bit: the reason this transformation is interesting is that in algorithms to identify the Pareto frontier, you don't care about absolute values of a coordinate, just its ordinal value with respect to other values in a column. Once transformed, a bunch of shortcuts and interesting properties open up.

Answer 3

If the number of possible points is large, than enumerating them all and taking a random sample won't be feasible. For example, suppose you have integer points in a 1000 x 1000 x 1000 box. Then, the number of possible points is 10^9, and it is unlikely that your computer will be able to generate the full list. Instead, it makes sense to index the points, and take a random sample of the indices, and then convert the indices to a point. For instance, in this example, there are 10^9 indices, and we can convert any index to a point using IntegerDigits, for example:

IntegerDigits[13412343, 1000]

{13, 412, 343}

So, to find 10 random sample indices, we can do:

SeedRandom[1]
indices = RandomSample[0 ;; 10^9-1, 10]

{877665282, 101700636, 562018428, 288541214, 403280597, 238031837, 817685571, \ 339828267, 510012226, 749565074}

The key here is that RandomSample can accept a span object instead of a list of 10^9 integers. Then, convert them to points with IntegerDigits:

IntegerDigits[indices, 1000]

{{877, 665, 282}, {101, 700, 636}, {562, 18, 428}, {288, 541, 214}, {403, 280, 597}, {238, 31, 837}, {817, 685, 571}, {339, 828, 267}, {510, 12, 226}, {749, 565, 74}}