Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generate multiple sequences of numbers with unique values at each index

I have a row with numbers 1:n. I'm looking to add a second row also with the numbers 1:n but these should be in a random order while satisfying the following:

  1. No positions have the same number in both rows
  2. No combination of numbers occurs twice

For example, in the following

Row 1:  1  2  3  4  5  6  7 ...
Row 2:  3  6  15 8  13 12 7 ...  

the number 7 occurs at the same position in both rows 1 and 2 (namely position 7; thereby not satisfying rule 1)

while in the following

Row 1:  1  2  3  4  5  6  7 ...
Row 2:  3  7  15 8  13 12 2 ...

the combination of 2+7 appears twice (in positions 2 and 7; thereby not satisfying rule 2).

It would perhaps be possible – but unnecessarily time-consuming – to do this by hand (at least up until a reasonable number), but there must be quite an elegant solution for this in MATLAB.

like image 810
rvrvrv Avatar asked Oct 10 '22 00:10

rvrvrv


1 Answers

This problem is called a derangment of a permutation.
Use the function randperm, in order to find a random permutation of your data.

x = [1  2  3  4  5  6  7];
y = randperm(x);

Then, you can check that the sequence is legal. If not, do it again and again..
You have a probability of about 0.3 each time to succeed, which means that you need roughly 10/3 times to try until you find it. Therefore you will find the answer really quickly.

Alternatively, you can use this algorithm to create a random derangment.

Edit

If you want to have only cycles of size > 2, this is a generalization of the problem. In it is written that the probability in that case is smaller, but big enough to find it in a fixed amount of steps. So the same approach is still valid.

like image 68
Andrey Rubshtein Avatar answered Oct 18 '22 07:10

Andrey Rubshtein