Take a random draw of all possible pairs of indices in Matlab

user_9947624 0
Viewed 83

Consider a Matlab matrix B which lists all possible unordered pairs (without repetitions) from [1 2 ... n]. For example, if n=4,

B=[1 2;
   1 3;
   1 4;
   2 3;
   2 4;
   3 4]

Note that B has size n(n-1)/2 x 2

I want to take a random draw of m rows from B and store them in a matrix C. Continuing the example above, I could do that as

m=2;
C=B(randi([1 size(B,1)],m,1),:);

However, in my actual case, n=371293. Hence, I cannot create B and, then, run the code above to obtain C. This is because storing B would require a huge amount of memory.

Could you advise on how I could proceed to create C, without having to first store B? Comments on a different question suggest to

  1. Draw at random m integers between 1 and n(n-1)/2.

    I=randi([1 n*(n-1)/2],m,1);

  2. Use ind2sub to obtain C.

Here, I'm struggling to implement the second step.

Thanks to the comments below, I wrote this

n=4;
m=10;
coord=NaN(m,2);
R= randi([1 n^2],m,1);
for i=1:m
    [cr, cc]=ind2sub([n,n],R(i));
    if cr>cc
       coord(i,1)=cc;
       coord(i,2)=cr;
    elseif cr<cc
       coord(i,1)=cr;
       coord(i,2)=cc;
    end
end
coord(any(isnan(coord),2),:) = []; %delete NaN rows from coord

I guess there are more efficient ways to implement the same thing.

matlab
2 Answers

You can use the function named myind2ind in this post to take random rows of all possible unordered pairs without generating all of them.

function [R , C] = myind2ind(ii, N)
    jj = N * (N - 1) / 2 + 1  - ii;
    r = (1 + sqrt(8 * jj)) / 2;
    R = N  -floor(r);
    idx_first = (floor(r + 1) .* floor(r)) / 2;
    C = idx_first-jj + R + 1;
end

I=randi([1 n*(n-1)/2],m,1);
[C1 C2] = myind2ind (I, n);
user_65797440

If you look at the odds, for i=1:n-1, the number of combinations where the first value is equal to i is (n-i) and the total number of cominations is n*(n-1)/2. You can use this law to generate the first column of C. The values of the second column of C can then be generated randomly as integers uniformly distributed in the range [i+1, n]. Here is a code that performs the desired tasks:

clc; clear all; close all;

% Parameters
n = 371293; m = 10;

% Generation of C
R = rand(m,1);
C = zeros(m,2);
s = 0;
t = n*(n-1)/2;
for i=1:n-1
    if (i<n-1)
        ind_i = R>=s/t & R<(s+n-i)/t;
    else % To avoid rounding errors for n>>1, we impose (s+n-i)=t at the last iteration (R<(s+n-i)/t=1 always true)
        ind_i = R>=s/t;
    end
    C(ind_i,1) = i;
    C(ind_i,2) = randi([i+1,n],sum(ind_i),1);
    s = s+n-i;
end

% Display
C

Output:

C =
       84333      266452
       46609      223000
      176395      328914
       84865       94391
      104444      227034
      221905      302546
      227497      335959
      188486      344305
      164789      266497
      153603      354932

Good luck!

user_66833220
Related