algorithm to find n unique randomly selected coordinates

Question

I need a way to check that the coordinates of n points bound by ( 0 <= x <= 4 and ( 0 <= y <= 4 ) are unique i.e. no two pints have the same coordinate pairs.

But here is the catch:

The number of points are determined at run time and can be from 1 to n (well let's say <= 10). The coordinates are selected randomly x = rand(0,4) and y = rand(0,4)

P.S. I am using the makecode block based coding for this project and the LED are on the microbit V1. So the above code has been converted from blocks to python by makecode.

Thanks

while index22 < level:  # level determines how many points I need to generate max 10
            listx[index22] = randint(0, 4)
            listy[index22] = randint(0, 4)
            led.plot(listx[index22], listy[index22])  # turns on an LED at the coordinate value
            index22 = index22 + 1

I am stumped beyond this..

Answer 1

Since you've only shown python code, I'm operating on the assumption that a possible solution expressed in python will be acceptable as well.

Guaranteeing the uniqueness of integers is easier than guaranteeing uniqueness of multidimensional points. An ancient trick using integer division and modulo arithmetic allows us to map a single integer into unique indices. If we use python's random.sample() to get a specified sample without replacement from within the integer range, the following code pops out.

import random

level = 10

# there are 25 distinct points in a 5x5 grid, so we
# sample 'level' unique values in the range 0..24
for value in random.sample(range(25), level):
    print(value // 5, value % 5)   # map int to indices

I used print() so you could confirm the uniqueness of the solutions. Replace the print() with a call to led.plot() for your application.

---

The approach above can be generalized to non-square grids. We need to identify row and column sizes explicitly, and then the division and modulus operations are performed relative to the column size. The example which follows illustrate this by enumerating a 2x3 and then a 3x2 case. I've isolated the logic in a function and added a bounds check.

import random
import sys

def gen_grid(*, rows, cols, level):
    if level > rows * cols:
        print("can't generate more levels than number of elements", file=sys.stderr)
        exit()
    print(f"{rows}x{cols}\n---")
    for value in random.sample(range(rows * cols), level):
        print(value // cols, value % cols)

gen_grid(rows = 2, cols = 3, level = 2 * 3)
print()
gen_grid(rows = 3, cols = 2, level = 2 * 3)

which will produce results such as

2x3
---
0 2
0 0
1 2
0 1
1 1
1 0

3x2
---
0 0
2 0
1 1
2 1
0 1
1 0

Your actual output will vary due to the randomness in the sampling.

This uses python 3 features to enforce named arguments, but could easily be flipped back to use positional notation for python 2 compatibility.

---

If you're concerned that using random.sample() is just pushing the challenge under the hood, I agree but would point out that if python is allowed, use of python libraries should be as well. However, if you want a solution which is self-contained and does not use the random module, here goes.

One solution that can guarantee unique sequences is to implement a PRNG (pseudo-random number generator) which achieves the maximal cycle length possible over the target range. PRNGs that have a maximal cycle repeat values only after every other value in the range has been enumerated. Implementations for two different PRNG algorithms are given below.

The first is a linear congruential generator parameterized to have a cycle length of exactly 25.

def lcg(seed):
    while True:
        seed = (11 * seed + 13) % 25
        yield seed

This will generate unique values in the range [0,...,24] in a shuffled order if called fewer than 26 times. Note that changing the seed value does not change the sequence, it only changes the starting point within the cycle.

The second one is a xorshift PRNG. A k-bit generator has a cycle length of 2^k-1 and produces unique values in the range [1,...,2^k-1]. With appropriate shift parameters all non-zero values can be generated. (Shifting and XORing zero always results in another zero, hence the exclusion.) To make the results fall in the range [0,...,24], we use k=5, reject values greater than 25, and subtract 1.

def xorshift_5bit(seed = 1, upper_limit):
    upper_limit += 1
    while True:
        seed ^= seed << 3
        seed &= 31
        seed ^= seed >> 2
        seed &= 31
        seed ^= seed << 4
        seed &= 31
        if seed < upper_limit:
            yield seed - 1

Note that by changing the value of upper_limit this can be used for any grid sizes below 31, although the number of rejections will increase for smaller grids. By contrast, the LCG is hard-wired to 25 and new coefficients would have to be determined for other grid sizes.

The resulting integer outcomes can be decomposed into grid indices as described earlier after a slight modification of the original code:

def gen_grid(*, rows, cols, level, seed):
    gen_rand = xorshift_5bit(seed, upper_limit = rows * cols)
    for _ in range(level):
        value = next(gen_rand)
        print(value // cols, value % cols)

Replace xorshift_5bit(seed, upper_limit = rows * cols) with lcg(seed) if you like LCGs better. Xorshift uses very efficient bitwise operations, but rejects 6/31 of the outcomes, while the LCG uses the relatively slow modulus operation but keeps all results due to tuning of the parameters. My timings with hyperfine showed the two to be indistinguishable.

Note that we no longer need restrict limit relative to rows * cols. The generators are infinite, we just have to acknowledge that the sequence will start repeating.