Is there an algorithm for generating random pairs of a set of numbers?

Question

0.00/5 (No votes)

See more:

I have a discontinuous list of numbers N (e.g. { 1, 2, 3, 6, 8, 10}) and i need to progressively create random pairs of numbers in N and store them in a list in which there can't be twice the same pair.

For example for a list of 3 different of numbers there is 6 possible pair (not counting same number pair):

example for the list { 4, 8, 9 }, the possible pairs are:

> (4,8) (4,9) (8,4) (8,9) (9,4) (9,8)

When we arrive to a number list size of 30 for example, we get 870 possible pairs and with my current method I get less and less efficient the more possible pairs there are.

What I have tried:

For now my strategy with a number list of size 30 for example is :

N = { 3, 8, 10, 15, 16, ... } // size = 30

// Lets say I have already a list with 200 different pairs
my_pairs = { (8,16), (23, 32), (16,10), ... }

// Get two random numbers in the list
rn1 = random(N)
rn2 = random(N)

Loop through my_pairs to see if the pair (rn1,rn2) has already been generated

If there is one, we pick two new numbers rn1 & rn2 at random and retry adding them to my_pairs

If not then we add it to the list

The issue is that the more pairs we have in my_pairs, the less likely it is for a pair to not be in that list. So we have to check multiple random pairs multiple times and go through the list every time.

I could try to generate all possible pairs at the start, shuffle the list and pop one element each time I need to add a random pair to my list.

But it will take a lot of space to store all possible pairs when my Numbers list size is increasing (like 9900 possible pairs for 100 different numbers).

And I add numbers in N during my process so I can't afford to recalculate all possible pairs every time.

Is there an algorithm for generating random unique pairs ?

Maybe it would be faster using matrices or storing my pairs in some sort of a tree graph ?

Posted 25-Aug-21 19:38pm

Member 12085717

Updated 7-Jan-22 1:02am

v5

Add a Solution

Comments

Peter_in_2780 26-Aug-21 3:18am

Sounds like a job for a 2D array (matrix), call it M. Generate x, y as your new random pair. If M(x,y) is not set, then (x,y) is a good new pair. Set M(x,y) and continue. If you don't care about the order of your pairs, you don't even need the list. You can just scan M and find the set elements after you've set enough.

Member 12085717 26-Aug-21 4:28am

But I think there is an issue if I use the coordinate of the 2D matrix to make my pairs because the pairs are made from a list N of discontinuous numbers, so I can have a list N like { 2, 300, 369 } (extreme case) which is not really translatable into a 2D matrix.

Member 12085717 26-Aug-21 4:29am

Actually, I just realized that I can use the numbers index in N as coordinate for the matrix, my bad. I will try this method see if it perform better.

Annaarddy 7-Jan-22 6:57am

Can you please provide your code which will useful for me. Thank you (Member 12085717)

CHill60 7-Jan-22 9:33am

I strongly advise you to remove this comment. This is an open forum and spam bots could easily extract your email address and start spamming you

Annaarddy 7-Jan-22 10:14am

Thank you

3 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2021-08-25T23:10:00

Quote:
I could try to generate all possible pairs at the start, shuffle the list and pop one element each time I need to add a random pair to my list.

Shuffling the complete list is the best overall option.
Any other solution is a trade off, what you save at 1 point, you spend it bigger at another point.

CPallini · Answer 2 · 2021-08-26T00:20:00

Suppose you have a way to compute the n_th combination of two indices of your list. E.g.

list { 4, 8, 9 }

combination number    pair
 0                    (4,8)
 1                    (4,9)
 2                    (8,4)

Then you have two (or possible more...) options:

Start with an array containing all the combination numbers, then pick randomly them eventually removing the picked ones from the array
Do not use the array (if you cannot afford it), choose randomly a combination number, check if it wasn't already taken and store it (using a tree container for that)

Unfortunately, the above suggestions badly clash with your additional requirement of 'dinamically add items to the original list'.

Annaarddy · Answer 3 · 2022-01-07T01:02:00

Solution 3

Genetic algorithm will work for generating random pairs

Posted 7-Jan-22 1:02am

Annaarddy

Comments

Dave Kreskowiak 7-Jan-22 8:09am

Probably, but it's way too big of a hammer for this problem.

Is there an algorithm for generating random pairs of a set of numbers?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Is there an algorithm for generating random pairs of a set of numbers?

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us