Pseudorandom Pair Sampling Without Replacement

This is a simple and fast implementation of random pair sampling without replacement.

For example, let's say we have 1D data [1,2,3,...,10], and we want to sample 20 non-overlapping pairs and get something like (4,3), (8,2), (1,6), etc.

We assume that the order doesn't matter, i.e., (4,3) is the same as (3,4).

There are multiple ways to do this, but it can be quite slow when we try to sample many pairs from a large data.

So, I came up with a simple and fast method. The idea is as follows.

1. Randomly shuffle the data: 5 9 6 10 4 3 8 1 2 7.

2. Without replacement, randomly pick pairs of direct neighbors: (6,10), (3,8), (5,9), ..., (10,4).

3. Without replacement, randomly pick pairs with one in-between neighbor: (4,8), (5,6), (1,7), ..., (9,10).

4. Without replacement, randomly pick pairs with two in-between neighbors: (9,4), (3,2), (5,10), ..., (8,7).

5. Without replacement, randomly pick pairs with three, four, ..., etc. in-between neighbors. In the end, the final pair will be (5,7).

If you do this to pick large enough number of pairs, then you will eventually get every possible pairs.

You stop the process as soon as you obtain the desired number of pairs.

To further increase the "randomness", we even randomize the order of steps (between step 2-5).

This means that the following example can happen:

We first pick ALL random pairs with three in-between neighbors, and then ALL random pairs with five in-between neighbors, and then ALL random pairs of direct neighbors, and so on.