Generating parings of numbers and the pairs must not contain the same numbers

Dear Matlab folks!

In order to create a stimulus sequence for a psychological experiment, I have to generate 20 pseudorandom pairings of the numbers 1 to 20.

I did this the follwong way:

x=randperm(20)

y=x'

a=randperm(20)

b=a'

Pairings=[y b]

BUT: The pairings must not contain the same numbers!

Example:

1 3

4 18

9 12

6 6 <-- This must not happen!

.

.

.

Would somebody be so kind and tell me how to code this?

Best Regards!

Answer 1

[Bruno Luong]

Use derangement (randpermfull function used below)

n= 20;
D = [1:n; randpermfull(n)]'
R = D(randperm(n),:)

[Rupert Steinmeier]

Unfortunately, randpermfull doesn't work: "Unrecognized function or variable 'randpermfull'."

Do you know what could cause this?

[Bruno Luong]

I have put the link to the File Exchage for randpermfull, have you downloaded it?

[Rupert Steinmeier]

Sorry, I have overlooked that!

Anyway, I downloaded it and tried to run it in Matlab but I get the following error:

"Unrecognized function or variable 'permfulllfunction'.

Error in randpermfull (line 1)

permfulllfunction R = randpermfull(N)"

[Bruno Luong]

You have (unintentionally I suppose) modified the original FEX source code.Download it again cleanly.

[Rupert Steinmeier]

Now it works, thank you very much Bruno!

Answer 2

[Bruno Luong]

Not sure if you require each column is the set 1:20 if yes see my other answer. If not

upperbnd = 20;  % values in [1:upperbnd]
nsamples = 20;  % number of samples
k = 2;          % 2 for pairs
[~,R] = maxk(rand(nsamples,upperbnd),k,2)

[Rupert Steinmeier]

Actually, I think your other answer would be the correct one, since I indeed require every integer from 1 to 20 in each column and every integer just once.

But for some reason, the randpermfull function is not recognized in my Matlab.

Answer 3

[John D'Errico]

As Bruno has said, you are looking for pseudo-random derangements. So just to add some interesting information about derangements in general.

https://en.wikipedia.org/wiki/Derangement

Interestingly, we see the claim there that the number of derangements of n numbers is equal to the subfactorial(n), which in turn can be found as the nearest integer to factorial(n)/exp(1). The OEIS lists the numbers of derangements as a function of n.

https://oeis.org/A000166

vpa(factorial(sym(20))/exp(sym(1)),30)
ans =
895014631192902120.954455115924

We can think of that in simple terms. Suppose we gnerate a random permutation of the integers 1:n. What is now the probability that the random permutation is a derangement? Since the total number of permutations of n numbers is factorial(n), then we can see the probability that a given permutation is in fact a derangement is just approximately exp(-1).

If all you want it to generate ONE random derangement, the simple solution would then be a rejection scheme. Generate random permutations, throwing them away if any members of the sequence are repeated. A problem is if you want to generate a set of p random mutual derangments of the original set, thus all of which are also derangements of all other sets? This gets more difficult. That is, given the set of numbers 1:n, you cannot have more than n-1 such mutual derangements of the original set.

We can understand this if we start with one randomly generated derangement:

D =
     1     2     3     4     5     6     7     8     9    10
     8     6     9     3     1    10     2     7     4     5

Thus we would see that 1 can fall into only 9 possible locations for this to be a valid derangement. However, if we now choose a second set that is mutually a derangement to both of the first two sets:

D
D =
     1     2     3     4     5     6     7     8     9    10
     8     6     9     3     1    10     2     7     4     5
     2     9     4     6    10     7     1     3     5     8

We see that 1 can now fall in only 8 possible locations. After 9 such permutations

D
D =
     1     2     3     4     5     6     7     8     9    10
     8     6     9     3     1    10     2     7     4     5
     2     9     4     6    10     7     1     3     5     8
     6     4     7     8     9     2    10     5     1     3
     3    10     5     9     2     8     4     1     6     7
     4     3     6     5     7     1     9    10     8     2
     9     1     8     7     6     5     3     2    10     4
    10     8     2     1     3     4     5     6     7     9
     7     5     1    10     4     3     8     9     2     6
     5     7    10     2     8     9     6     4     3     1

there can no longer be any valid additionally mutual derangemements. As we see above, a 10x10 matrix that has a 1 in every columns and a 1 in every row. The same applies to the number 2, as well as 3, etc. Logically, I could never add even one more row to this array. The above array was not that difficult to generate, since there are only factorial(10)=3628800 possible permutations of 10 numbers.