Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Random number generation with specified separation

Subject: Random number generation with specified separation

From: Anindya G

Date: 18 Apr, 2013 18:37:17

Message: 1 of 8

Hello,

I want to generate n (uniformly distributed) random numbers in a particular interval (say [a b]) such that the resulting numbers are separated from each other by at least "delta".

I know that I can generate uniformly distributed random numbers using 'rand'. Further, to generate n numbers in interval [a b], I should use:
 r = a + (b-a).*rand(n,1);

However, I can't figure out how to specify that the n random numbers should have a minimal separation of delta. I tried looking up on the group here but didn't find any solution. Any help would be greatly appreciated.

Anindya.

Subject: Random number generation with specified separation

From: dpb

Date: 18 Apr, 2013 19:00:23

Message: 2 of 8

On 4/18/2013 1:37 PM, Anindya G wrote:
> Hello,
>
> I want to generate n (uniformly distributed) random numbers in a
> particular interval (say [a b]) such that the resulting numbers are
> separated from each other by at least "delta".
> I know that I can generate uniformly distributed random numbers using
> 'rand'. Further, to generate n numbers in interval [a b], I should use:
> r = a + (b-a).*rand(n,1);
>
> However, I can't figure out how to specify that the n random numbers
> should have a minimal separation of delta. I tried looking up on the
> group here but didn't find any solution. Any help would be greatly
> appreciated.

Rather unusual request and, of course, the result isn't likely to be
random if tested by the usual methods prng's undergo...

Only idea that comes to mind is a generation/rejection method. Generate
a sample and test for your criterion; regenerate values for those that
fail. Repeat until success...

--

Subject: Random number generation with specified separation

From: dpb

Date: 18 Apr, 2013 19:05:05

Message: 3 of 8

On 4/18/2013 2:00 PM, dpb wrote:
...

> Only idea that comes to mind is a generation/rejection method. Generate
> a sample and test for your criterion; regenerate values for those that
> fail. Repeat until success...

That could be as crude as simply "adjusting" a value that misses by a
factor that brings it into compliance w/o actually regenerating a value.
  Should be as good as any other value selected to force such a
criterion as far as properties go.

--

Subject: Random number generation with specified separation

From: Kumar Vijay Mishra

Date: 18 Apr, 2013 20:24:10

Message: 4 of 8

"Anindya G" wrote in message <kkpegs$m9q$1@newscl01ah.mathworks.com>...
> Hello,
>
> I want to generate n (uniformly distributed) random numbers in a particular interval (say [a b]) such that the resulting numbers are separated from each other by at least "delta".
>
> I know that I can generate uniformly distributed random numbers using 'rand'. Further, to generate n numbers in interval [a b], I should use:
> r = a + (b-a).*rand(n,1);
>
> However, I can't figure out how to specify that the n random numbers should have a minimal separation of delta. I tried looking up on the group here but didn't find any solution. Any help would be greatly appreciated.
>
> Anindya.

What you can possibly do is divide your interval [a, b] in several subintervals each of length delta/2. Randomly pick a subinterval and randomly choose a number from that subinterval. Now leave aside the immediate neighboring subintervals, and then randomly pick any other subinterval and a number from that subinterval. Continue picking sunintervals and numbers like this until you reach n (while also keeping track of the fact that you should not pick a number from the same subinterval again).

Kumar Vijay Mishra.

Subject: Random number generation with specified separation

From: dpb

Date: 18 Apr, 2013 20:43:33

Message: 5 of 8

On 4/18/2013 3:24 PM, Kumar Vijay Mishra wrote:
> "Anindya G" wrote in message <kkpegs$m9q$1@newscl01ah.mathworks.com>...
...

>> I want to generate n (uniformly distributed) random numbers in a
>> particular interval (say [a b]) such that the resulting numbers are
>> separated from each other by at least "delta".
...

> What you can possibly do is divide your interval [a, b] in several
> subintervals each of length delta/2. Randomly pick a subinterval and
> randomly choose a number from that subinterval. Now leave aside the
> immediate neighboring subintervals, and then randomly pick any other
> subinterval and a number from that subinterval. Continue picking
> sunintervals and numbers like this until you reach n (while also keeping
> track of the fact that you should not pick a number from the same
> subinterval again).
>
> Kumar Vijay Mishra.

Don't see that working...if you start in interval 1, say, then may as
well go thru the next odd intervals and then you'll end up w/ N/2 total.
  Any that are picked in the even intervals will be <delta apart from
the previous since the max distance between boundaries is 2*(D/2)=D, any
two that are adjoining within those subintervals have to be within D of
each other. Unless I'm missing something in the description, here...

--

Subject: Random number generation with specified separation

From: Bruno Luong

Date: 20 Apr, 2013 07:52:07

Message: 6 of 8

I'll give solution for (a,b) = (0,1). It is easy to map the results to the interval (a,b). You need to use some tools (MergeBrackets and RangeIntersection) I have developped:

function [lower upper] = MergeBrackets(left, right)
% function [lower upper] = MergeBrackets(left, right)
%
% Purpose: Interval merging
%
% Given N input closed intervals in braket form:
% Ii := [left(i),right(i)], i = 1,2...,N (mathematical notation)
% The set union{Ii) can be written as a canonical partition by
% intervals Jk; i.e., union{Ii) = union(Jk), where Jk are M intervals
% (with M<=N, so the partition is minimum cardinal), and {Jk} are
% disjoint to each other (their intersections are empty). This function
% returns Jk = [lower(k),upper(k)], k=1,2,...M, in the ascending sorted
% order.
%
% EXAMPLE USAGE:
% >> [lower upper] = MergeBrackets([0 1 2 3 4],[1.5 1.6 3.5 3 5])
% lower = 0 2 4
% upper = 1.6 3.5 5
%
% Algorithm complexity: O(N*log(N))
%
% Author: Bruno Luong <brunoluong@yahoo.com>
% Original: 25-May-2009

% Detect when right < left (empty Ii), and later remove it (line #29, 30)
notempty = find(right>=left);

% sort the rest by left bound
[left iorder] = sort(left(notempty));
right = right(notempty(iorder));

% Allocate, as we don't know yet the size, we assume the largest case
lower = zeros(size(left));
upper = zeros(size(right));

% Nothing to do
if isempty(lower)
    return
end

% Initialize
l = left(1);
u = right(1);
k = 0;
% Loop on brakets
for i=1:length(left)
    if left(i) > u % new Jk detected
        % Stack the old one
        k = k+1;
        lower(k) = l;
        upper(k) = u;
        % Reset l and u
        l = left(i);
        u = right(i);
    else
        u = max(u, right(i));
    end
end % FOR loop
% Stack the last one
k = k+1;
lower(k) = l;
upper(k) = u;

% Remove the tails
lower(k+1:end) = [];
upper(k+1:end) = [];

end % MergeBrackets


function [l, r] = RangeIntersection(varargin)
% [l, r] = RangeIntersection(l1, r1, l2, r2, ... )
%
% Purpose: Intersection of n sets of interval-unions
%
% Given N sets of input closed interval-unions in braket form:
% I1 := [l1(i),r1(i)], i = 1,2...,M1
% ...
% In := [ln(j),rn(j)], j = 1,2...,Mn (mathematical notation)
% The set K = intersect(union{I1),...union{In)) can be written as a canonical
% partition by intervals Kk; i.e., union{Kk) = K, where Kk are P
% intervals and {Kk} are disjoint to each other (their intersections
% are empty).
% This function returns
% Kk = [l(k),r(k)], k=1,2,...P, in the ascending sorted order.
%
% EXAMPLE USAGE:
% >> [lower upper] = RangeIntersection([1 5], [3 9], 2, 8)
% lower = 2 5
% upper = 3 8
%
% Author: Bruno Luong <brunoluong@yahoo.com>
% Original: 19-April-2013

nset = length(varargin)/2;

if nset == 0
    l = [];
    r = [];
elseif nset == 1
    [l, r] = RI1(varargin{1:2});
else
    [l, r] = deal(varargin{1:2});
    for k = 2:nset
        [l, r] = RI2(l, r, varargin{2*k+(-1:0)});
    end
end

end % RangeIntersection

%%
function [l, r] = RI1(l, r)

[l, r] = MergeBrackets(l, r);

end % RI1

%%
function [l, r] = RI2(l1, r1, l2, r2)
% [l, r] = RI2(l1, r1, l2, r2)
%
% Purpose: Intersection of two sets of interval-unions
%
% Given M and N input closed intervals in braket form:
% Ii := [l1(i),r1(i)], i = 1,2...,M
% Jj := [l2(j),r2(j)], j = 1,2...,N (mathematical notation)
% The set K = intersect(union{Ii),union{Ii)) can be written as a canonical
% partition by intervals Kk; i.e., union{Kk) = K, where Kk are P
% intervals and {Kk} are disjoint to each other (their intersections
% are empty).
% This function returns
% Kk = [l(k),r(k)], k=1,2,...P, in the ascending sorted order.
%
% EXAMPLE USAGE:
% >> [lower upper] = RI2([1 5], [3 9], 2, 8)
% lower = 2 5
% upper = 3 8
%
% Author: Bruno Luong <brunoluong@yahoo.com>
% Original: 19-April-2013

intersect = ~(bsxfun(@lt, r1(:), l2(:)') | ...
              bsxfun(@gt, l1(:), r2(:)'));

[L1, L2] = ndgrid(l1,l2);
[R1, R2] = ndgrid(r1,r2);
l = max(L1(intersect),L2(intersect));
r = min(R1(intersect),R2(intersect));
[l, r] = MergeBrackets(l', r');

end % RI2


% Test on command line
delta = 0.07;
n = 10;

left = 0;
right = 1;
a = nan(1,n);
for k = 1:n
    d = right-left;
    if isempty(d)
        error('fail to generate, n or delta too large')
    end
    c = [0 cumsum(d)];
    s = c(end);
    c = c/s;
    r = rand();
    [~, i] = histc(r, c);
    ak = left(i) + (r-c(i))*s;
    a(k) = ak;
    [left, right] = RangeIntersection(left, right, ...
                                      [-Inf ak+delta], [ak-delta Inf], ...
                                      0, 1);
end

a % <- here is your random array of n points
all(diff(sort(a))> delta)

% Bruno

Subject: Random number generation with specified separation

From: Bruno Luong

Date: 20 Apr, 2013 08:04:10

Message: 7 of 8

Note that the method is far from perfect: the distribution is larger at the two ends {0 and 1} if n*delta is close to 1.

Otherwise it's pretty uniform.

Bruno

Subject: Random number generation with specified separation

From: Bruno Luong

Date: 22 Apr, 2013 11:35:09

Message: 8 of 8

I have simplified a code:

function [lower upper] = MergeBrackets(left, right)
% function [lower upper] = MergeBrackets(left, right)
%
% Purpose: Interval merging
%
% Given N input closed intervals in braket form:
% Ii := [left(i),right(i)], i = 1,2...,N (mathematical notation)
% The set union{Ii) can be written as a canonical partition by
% intervals Jk; i.e., union{Ii) = union(Jk), where Jk are M intervals
% (with M<=N, so the partition is minimum cardinal), and {Jk} are
% disjoint to each other (their intersections are empty). This function
% returns Jk = [lower(k),upper(k)], k=1,2,...M, in the ascending sorted
% order.
%
% EXAMPLE USAGE:
% >> [lower upper] = MergeBrackets([0 1 2 3 4],[1.5 1.6 3.5 3 5])
% lower = 0 2 4
% upper = 1.6 3.5 5
%
% Algorithm complexity: O(N*log(N))
%
% Author: Bruno Luong <brunoluong@yahoo.com>
% Original: 25-May-2009

% Detect when right < left (empty Ii), and later remove it (line #29, 30)
notempty = find(right>=left);

% sort the rest by left bound
[left iorder] = sort(left(notempty));
right = right(notempty(iorder));

% Allocate, as we don't know yet the size, we assume the largest case
lower = zeros(size(left));
upper = zeros(size(right));

% Nothing to do
if isempty(lower)
    return
end

% Initialize
l = left(1);
u = right(1);
k = 0;
% Loop on brakets
for i=1:length(left)
    if left(i) > u % new Jk detected
        % Stack the old one
        k = k+1;
        lower(k) = l;
        upper(k) = u;
        % Reset l and u
        l = left(i);
        u = right(i);
    else
        u = max(u, right(i));
    end
end % FOR loop
% Stack the last one
k = k+1;
lower(k) = l;
upper(k) = u;

% Remove the tails
lower(k+1:end) = [];
upper(k+1:end) = [];

end % MergeBrackets

%
function [l, r] = RangeIntersection(varargin)
% [l, r] = RangeIntersection(l1, r1, l2, r2, ... )
%
% Purpose: Intersection of n sets of interval-unions
%
% Given N sets of input closed interval-unions in braket form:
% I1 := [l1(i),r1(i)], i = 1,2...,M1
% ...
% In := [ln(j),rn(j)], j = 1,2...,Mn (mathematical notation)
% The set K = intersect(union{I1),...union{In)) can be written as a canonical
% partition by intervals Kk; i.e., union{Kk) = K, where Kk are P
% intervals and {Kk} are disjoint to each other (their intersections
% are empty).
% This function returns
% Kk = [l(k),r(k)], k=1,2,...P, in the ascending sorted order.
%
% EXAMPLE USAGE:
% >> [lower upper] = RangeIntersection([1 5], [3 9], 2, 8)
% lower = 2 5
% upper = 3 8
%
% Author: Bruno Luong <brunoluong@yahoo.com>
% Original: 19-April-2013

nset = length(varargin)/2;

if nset == 0
    l = [];
    r = [];
elseif nset == 1
    [l, r] = MergeBrackets(varargin{1:2});
else
    [l, r] = deal(varargin{1:2});
    for k = 2:nset
        [l, r] = RI2(l, r, varargin{2*k+(-1:0)});
    end
end

end % RangeIntersection

%%
function [l, r] = RI2(l1, r1, l2, r2)

l = bsxfun(@max, l1(:), l2(:)');
r = bsxfun(@min, r1(:), r2(:)');
intersect = l < r;
[l, r] = MergeBrackets(l(intersect)', r(intersect)');

end % RI2

%
function a = rand_minsep(n, delta)
% a = rand_minsep(n, delta)
%
% Generate n randomn values in (0,1) with do not collite with a tolerance tol
% i.e., all(diff(sort(a))>= delta) is true

left = 0;
right = 1;
a = nan(1,n);
for k = 1:n
    d = right-left;
    if isempty(d)
        error('fail to generate, n or delta too large')
    end
    c = [0 cumsum(d)];
    s = c(end);
    c = c/s;
    r = rand();
    [~, i] = histc(r, c);
    ak = left(i) + (r-c(i))*s;
    a(k) = ak;
    [left, right] = RangeIntersection(left, right, ...
                                      [-Inf ak+delta], [ak-delta Inf], ...
                                      0, 1);
end

end % rand_minsep

%%%%%%%%%%%%%%%%%%%%%%
% Test on command line
n = 100;
delta = 0.005;
a = rand_minsep(n, delta) % <- here is your random array of n points
all(diff(sort(a))> delta)

% Bruno

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us