# How to generate random points without duplication?

In generating a list of random 2D integral coordinates e.g. {{u1,v1}, {u2,v2}, {u3,v3},...}, how can one write a condition specifying that no point is repeated, i.e no {ui,vi} == {uj,vj}?

• ui, vi are real numbers? – kglr Jun 1 at 14:32
• Integers from 0 to 20, so it happens frequently. – spaced Jun 1 at 14:38
• To add more detail to the question - the points are being generated by an optimization routine (NMaximize); I think the only way I can control for duplicates is by specifying a constraint on the ui, vi being generated. – spaced Jun 1 at 14:55

If you only have 20 integers, you can proceed as in the other answers, and generate all possible tuples, and then sample randomly. On the other hand, if you have many more integers, you will not want to generate all possible tuples. For example, suppose you have 10^6 integers, and you want to guarantee that there are no duplicates. In this case, creating the list of 10^12 tuples will obviously not work.

In this case, you can create a function that converts between integers and tuples. For example, with integers from 0 to 999999, that function is QuotientRemainder. Since there are (10^6) * (10^6) tuples, we can construct a random sample of tuples with:

QuotientRemainder[RandomSample[0 ;; 10^12-1, 20], 10^6]


{{907983, 133497}, {517855, 551768}, {630894, 992111}, {729528, 990425}, {908605, 700641}, {109298, 886800}, {419959, 75716}, {829838, 303614}, {629060, 96075}, {302111, 741921}, {173138, 477425}, {89844, 799405}, {738388, 606520}, {419960, 677229}, {708126, 327841}, {420295, 191655}, {32408, 973949}, {181724, 12744}, {203054, 506577}, {288186, 436908}}

Here's a comparison with the Tuples approach:

SeedRandom[1]
r1 = QuotientRemainder[RandomSample[0 ;; 440, 20], 21]

SeedRandom[1]
r2 = RandomSample[Tuples[Range[0,20],2],20]

r1 === r2


{{19, 19}, {12, 5}, {18, 6}, {6, 8}, {1, 10}, {16, 0}, {10, 18}, {4, 11}, {5, 19}, {6, 11}, {14, 6}, {15, 8}, {19, 9}, {0, 19}, {3, 12}, {8, 1}, {18, 18}, {0, 9}, {9, 3}, {19, 6}}

{{19, 19}, {12, 5}, {18, 6}, {6, 8}, {1, 10}, {16, 0}, {10, 18}, {4, 11}, {5, 19}, {6, 11}, {14, 6}, {15, 8}, {19, 9}, {0, 19}, {3, 12}, {8, 1}, {18, 18}, {0, 9}, {9, 3}, {19, 6}}

True

And, a timing comparison for integers from 0 to 1000:

SeedRandom[1]
r1 = QuotientRemainder[RandomSample[0 ;; 1001^2-1, 20], 1001]; //AbsoluteTiming

SeedRandom[1]
r2 = RandomSample[Tuples[Range[0, 1000], 2], 20]; //AbsoluteTiming

r1 === r2


{0.000042, Null}

{0.003316, Null}

True

• +1. I was going to do the same thing with IntegerDigits. – Michael E2 Jun 2 at 4:20
• @MichaelE2 IntegerDigits is a much better idea, as it works with higher order tuples, i.e., 3-tuples instead of 2-tuples. – Carl Woll Jun 2 at 4:37
• @MichaelE2 Please show your IntegerDigits-approach, sounds interesting. Thanks. – Ulrich Neumann Jun 2 at 17:40
• @UlrichNeumann Just change QuotientRemainder[xxx, base] to IntegerDigits[xxx, base, 2]. Change the 2 to a 3 to get 3-tuples and so forth. I didn't think it was sufficiently different than Carl's answer to warrant a separate answer. Was I wrong? – Michael E2 Jun 2 at 18:02
• @MichaelE2 I got it, thank you! – Ulrich Neumann Jun 2 at 20:19
RandomSample[Tuples[Range[0, 20], 2], 10]


{{14, 13}, {2, 17}, {12, 7}, {1, 11}, {6, 6}, {12, 4}, {13, 14}, {2, 16}, {15, 6}, {1, 0}}

Note: The length of the sample cannot exceed 21^2 (441).

Since you mentioned that your coordinates are drawn from integers in the regions 20 >= u >= 0 and 20 >= v >= 0, you can first generate a one-dimensional vector containing all lattice points:

V = Flatten[Table[x[i,j],{i,0,20},{j,0,20}]];


Then you can select a random sample from this vector, e.g.:

RandomSample[V,5]/.x->List


{{16, 8}, {10, 17}, {8, 5}, {0, 17}, {16, 9}}

Since V has no duplicates, the random sample will also contain no duplicates.

• Or even like this: RandomSample[Flatten[Table[{x, y}, {x, 0, 20}, {y, 20}], 1], 5]. – kirma Jun 1 at 14:50
• Or... RandomSample[{x, y} /. Solve[(x | y) \[Element] Integers, {x, y} \[Element] Rectangle[{0, 0}, {20, 20}]], 10] – kirma Jun 1 at 14:54

For 10 points, oversample and select unique ones using RandomSample.

points = RandomInteger[20, {50, 2}];
points = RandomSample[points, 10]


Actually, RandomInteger[20, {50, 2}] appear to produce 50 unique 2D points.

E.g.

tries = 0;
points = RandomInteger[20, {50, 2}];
While[(sample = Quiet[Check[RandomSample[points, 50], True]]),
tries++;]
tries


0

• This doesn't guarantee success. A better approach is probably something like RandomSample[Range[0,20],10], right? – AccidentalFourierTransform Jun 1 at 14:43

It kind of depends on what you want to do next. You only need to generate one such list, and only once? Then efficiency is not important, and so you can proceed very naively as follows: generate random lists until one works:

Module[{l = RandomInteger[{0, 20}, {10, 2}]},
While[Length[l] != Length[DeleteDuplicates[l]],
l = RandomInteger[{0, 20}, {10, 2}]];
l
]


On the other hand, if you need many of these lists, then a more efficient approach is as follows: first generate all possible pairs, and pick a random sample ever time you need one such list:

lists = Tuples[Range[0, 20], 2];
sample := RandomSample[lists,10];


Now every time you execute sample you will get one such list, picked at random.