Got Questions? Get Answers.
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 Integers Within Specfic Ranges

Subject: Random Integers Within Specfic Ranges

From: RogerB .

Date: 11 Mar, 2011 15:51:04

Message: 1 of 19

Hi,
I can generate random integers within a range (say A to B), its no problem. What I want to do is generate a series of number one after the other. For example:
Generate five numbers between 1 and 20.
Range is between 1 and 20,
When the first integer is generated the second one cannot be the same as the first one and the third one cannot be the same as the first one or second one and so on.
So the output matrix could look something like this
10-4-6-14-2
8-17-16-6-1
2-19-14-4-5
7-19-15-3-20
4-2- 20-9-17
18-7-9-11-10
And so on.
When I use the rand function I can generate the five numbers within the range but the numbers can repeat themselves, I want to avoid this.
How can I close out part of the range for the next number to be generated.
So in the case of the range (1-20) the rand function generates a number between 0-1 and multiplies it by 20 and rounds it. If the first of the five numbers is 10, how can I get the second number to fall, uniformly, in the remaining two ranges (1-9) and (11-20) and so on?

Thanks inadvance!

Subject: Random Integers Within Specfic Ranges

From: Nasser M. Abbasi

Date: 11 Mar, 2011 16:07:14

Message: 2 of 19

On 3/11/2011 7:51 AM, RogerB . wrote:
> Hi,
> I can generate random integers within a range (say A to B), its no problem. What I want to do
> is generate a series of number one after the other. For example:
> Generate five numbers between 1 and 20.
> Range is between 1 and 20,
> When the first integer is generated the second one cannot be the same as the first one and
> the third one cannot be the same as the first one or second one and so on.
> So the output matrix could look something like this
> 10-4-6-14-2
> 8-17-16-6-1
> 2-19-14-4-5
> 7-19-15-3-20
> 4-2- 20-9-17
> 18-7-9-11-10
> And so on.
> When I use the rand function I can generate the five numbers within the range but
>the numbers can repeat themselves, I want to avoid this.
> How can I close out part of the range for the next number to be generated.
> So in the case of the range (1-20) the rand function generates a number between 0-1
> and multiplies it by 20 and rounds it. If the first of the five numbers is 10, how can
>I get the second number to fall, uniformly, in the remaining two ranges (1-9) and (11-20) and so on?
>
> Thanks inadvance!

can you use randperm?

do randperm(20), then take the first 5 numbers or any 5 will do, since
all random.

do that again, as many times. randperm will not duplicate numbers
in its result.

EDU>> randperm(5)
      2 3 4 1 5
EDU>> randperm(5)
      3 4 5 2 1
EDU>> randperm(5)
      4 2 3 1 5
EDU>> randperm(5)
      2 3 1 5 4


--Nasser

Subject: Random Integers Within Specfic Ranges

From: Roger Stafford

Date: 11 Mar, 2011 21:17:07

Message: 3 of 19

"RogerB ." wrote in message <ildgd8$dhl$1@fred.mathworks.com>...
> Hi,
> I can generate random integers within a range (say A to B), its no problem. What I want to do is generate a series of number one after the other. For example:
> Generate five numbers between 1 and 20.
> Range is between 1 and 20,
> When the first integer is generated the second one cannot be the same as the first one and the third one cannot be the same as the first one or second one and so on.
> So the output matrix could look something like this
> 10-4-6-14-2
> 8-17-16-6-1
> 2-19-14-4-5
> 7-19-15-3-20
> 4-2- 20-9-17
> 18-7-9-11-10
> And so on.
> When I use the rand function I can generate the five numbers within the range but the numbers can repeat themselves, I want to avoid this.
> How can I close out part of the range for the next number to be generated.
> So in the case of the range (1-20) the rand function generates a number between 0-1 and multiplies it by 20 and rounds it. If the first of the five numbers is 10, how can I get the second number to fall, uniformly, in the remaining two ranges (1-9) and (11-20) and so on?
>
> Thanks inadvance!
- - - - - - - - - -
  The following will make fewer calls on 'rand' than 'randperm' and it does not do a sort (though it may be slower nevertheless.) The n-length rows of the output array x will be given non-repeating integers selected randomly from 1:N. We must therefore have n <= N. This is repeated for each of the m rows of x.

x = zeros(m,n);
p = zeros(1,N);
for j = 1:m
 p(1:N) = 1:N;
 for k = N:-1:N-n+1
  q = ceil(k*rand);
  x(j,N-k+1) = p(q);
  p(q:k-1) = p(q+1:k);
 end
end

Roger Stafford

Subject: Random Integers Within Specfic Ranges

From: Jan Simon

Date: 11 Mar, 2011 23:28:05

Message: 4 of 19

Dear RogerB,

For small vectors RANDPERM is fine. For larger vectors, the C-Mex Shuffle can save processing time:
  http://www.mathworks.com/matlabcentral/fileexchange/27076-shuffle

Kind regards, Jan

Subject: Random Integers Within Specfic Ranges

From: David Dresden

Date: 12 Mar, 2011 02:22:05

Message: 5 of 19

Well what happens if your first number you generate is like 17? You'd never be able to generate 5 numbers all less than 20 but > 17.

Subject: Random Integers Within Specfic Ranges

From: Roger Stafford

Date: 12 Mar, 2011 03:47:06

Message: 6 of 19

"David Dresden" <liquidnitrogenoverclocking@hushmail.com> wrote in message <ilelcd$b5f$1@fred.mathworks.com>...
> Well what happens if your first number you generate is like 17? You'd never be able to generate 5 numbers all less than 20 but > 17.
- - - - - - - - - - -
  David, if you were referring to my code, yes, I didn't adhere to the original request and simply used the range 1:N. Below the code is modified to choose m rows of n random distinct integers in the range A:B. Of course we must have n <= B-A+1.

x = zeros(m,n);
N = B-A+1;
p = zeros(1,N);
for j = 1:m
 p(1:N) = A:B;
 for k = N:-1:N-n+1
  q = ceil(k*rand);
  x(j,N-k+1) = p(q);
  p(q:k-1) = p(q+1:k);
 end
end

  Note: As I indicated earlier, this is very likely not optimum code. I was experimenting with avoiding a sort operation and keeping the calls on 'rand' to a minimum.

Roger Stafford

Subject: Random Integers Within Specfic Ranges

From: Bruno Luong

Date: 12 Mar, 2011 07:15:22

Message: 7 of 19

"Roger Stafford" wrote in message <ileqbq$s0e$1@fred.mathworks.com>...

>
> x = zeros(m,n);
> N = B-A+1;
> p = zeros(1,N);
> for j = 1:m
> p(1:N) = A:B;
> for k = N:-1:N-n+1
> q = ceil(k*rand);
> x(j,N-k+1) = p(q);
> p(q:k-1) = p(q+1:k);
> end
> end
>
> Note: As I indicated earlier, this is very likely not optimum code. I was experimenting with avoiding a sort operation and keeping the calls on 'rand' to a minimum.

Roger, I guess the bigger time spend i your code is in the statement
p(q:k-1) = p(q+1:k);

If the array would be stored as chain-list rather than contiguous, moving the block will cost constant time. Unfortunately Matlab does not offer such data structure.

It looks like the method you propose is best in term of complexity if such list is used. Knuth's method has similar best complexity, but it's even simpler in term of implementation on computer.

Bruno

Subject: Random Integers Within Specfic Ranges

From: Roger Stafford

Date: 12 Mar, 2011 08:59:05

Message: 8 of 19

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ilf6ia$r0f$1@fred.mathworks.com>...
> "Roger Stafford" wrote in message <ileqbq$s0e$1@fred.mathworks.com>...
> .......
> > p(q:k-1) = p(q+1:k);
> > ......
>
> Roger, I guess the bigger time spend i your code is in the statement
> p(q:k-1) = p(q+1:k);
>
> If the array would be stored as chain-list rather than contiguous, moving the block will cost constant time. Unfortunately Matlab does not offer such data structure.
>
> It looks like the method you propose is best in term of complexity if such list is used. Knuth's method has similar best complexity, but it's even simpler in term of implementation on computer.
>
> Bruno
- - - - - - - - - -
  Yes, I should have used this instead:

 p(q) = p(k);

That would work just as well and it would change it from O(N^2) to O(N).

Roger Stafford

Subject: Random Integers Within Specfic Ranges

From: Bruno Luong

Date: 12 Mar, 2011 09:25:04

Message: 9 of 19

"Roger Stafford" wrote in message <ilfckp$rs1$1@fred.mathworks.com>...

> Yes, I should have used this instead:
>
> p(q) = p(k);
>
> That would work just as well and it would change it from O(N^2) to O(N).
>
> Roger Stafford

The small change makes the algo become much better. Thanks.

Bruno

Subject: Random Integers Within Specfic Ranges

From: Derek O'Connor

Date: 12 Mar, 2011 14:15:07

Message: 10 of 19

"RogerB ." wrote in message <ildgd8$dhl$1@fred.mathworks.com>...
> Hi,
> I can generate random integers within a range (say A to B), its no problem. What I want to do is generate a series of number one after the other. For example:
> Generate five numbers between 1 and 20.
> Range is between 1 and 20,
> When the first integer is generated the second one cannot be the same as the first one and the third one cannot be the same as the first one or second one and so on.
---snip ---

This is a minor variation on Durstenfeld's implementation of the Fisher-Yates Shuffle, referred to by Jan Simon above, and is similar to Roger Stafford's method. It generates a random sample of size m from the range of integers L:U, without replacement.

-----------------------------------------------------
function p = GRPfysLUM(L,U,m);
n = U-L+1;
p = L:U; % Start with complete range and then randomly shuffle these integers
for k = 2:n
     r = ceil(rand*k);
     t = p(k);
     p(k) = p(r);
     p(r) = t;
end
p = p(1:m); % return the first m as the sample.

----------------------------------------------------

The complexity of this function is O(n).

If m is approx. equal to n then this method is optimal. If m is much smaller than n then there are two obvious inefficiencies: (1) a vector p of size n is used, and (2) the for-loop takes n-1 steps.

Is there an optimum algorithm for all m <= n or otherwise?

Derek O'Connor.

Subject: Random Integers Within Specfic Ranges

From: Bruno Luong

Date: 12 Mar, 2011 14:53:04

Message: 11 of 19

"Derek O'Connor" wrote in message <ilfv5b$6pa$1@fred.mathworks.com>...

>
> If m is approx. equal to n then this method is optimal. If m is much smaller than n then there are two obvious inefficiencies: (1) a vector p of size n is used, and (2) the for-loop takes n-1 steps.
>

Storing full p seems to be unavoidable in Roger's method.
The point (2) is not a point, just iterate m time then stop.

Bruno

Subject: Random Integers Within Specfic Ranges

From: Derek O'Connor

Date: 12 Mar, 2011 17:36:04

Message: 12 of 19

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ilg1cg$r6q$1@fred.mathworks.com>...
> "Derek O'Connor" wrote in message <ilfv5b$6pa$1@fred.mathworks.com>...
>
> >
> > If m is approx. equal to n then this method is optimal. If m is much smaller than n then there are two obvious inefficiencies: (1) a vector p of size n is used, and (2) the for-loop takes n-1 steps.
> >
>
> Storing full p seems to be unavoidable in Roger's method.
> The point (2) is not a point, just iterate m time then stop.
>
> Bruno

Bruno,

Point (2) is a point.

for k = 2:m does not work. Note the first statement in the for k-loop: r = ceil(rand*k);

For example let L = -50, U = 50, and m = 3. This means that only the first 3 elements of p = [-50 -49 -48 -47 .. 59 50] get shuffled and we get p = [p1 p2 p3 -47..50]. Thus a random sample of the numbers -50, -49, -48 is returned instead of something such as
-42 39 -29 which is one of the samples which GRPfysLUM(-50,50,3) returns.

Derek O'Connor.

Subject: Random Integers Within Specfic Ranges

From: Bruno Luong

Date: 12 Mar, 2011 18:52:07

Message: 13 of 19

Derek wrote:
>
> Point (2) is a point.
>

Not to me:

x = zeros(1,m);
p = 1:N;
for k = N:-1:N-m+1
    q = ceil(k*rand);
    x(N-k+1) = p(q);
    p(q) = p(k);
end

% Bruno

Subject: Random Integers Within Specfic Ranges

From: Roger Stafford

Date: 12 Mar, 2011 18:56:04

Message: 14 of 19

"Derek O'Connor" wrote in message <ilgau4$5hb$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ilg1cg$r6q$1@fred.mathworks.com>...
> > "Derek O'Connor" wrote in message <ilfv5b$6pa$1@fred.mathworks.com>...
> > > If m is approx. equal to n then this method is optimal. If m is much smaller than n then there are two obvious inefficiencies: (1) a vector p of size n is used, and (2) the for-loop takes n-1 steps.
> >
> > Storing full p seems to be unavoidable in Roger's method.
> > The point (2) is not a point, just iterate m time then stop.
> >
> > Bruno
>
> Bruno,
>
> Point (2) is a point.
>
> for k = 2:m does not work. Note the first statement in the for k-loop: r = ceil(rand*k);
>
> For example let L = -50, U = 50, and m = 3. This means that only the first 3 elements of p = [-50 -49 -48 -47 .. 59 50] get shuffled and we get p = [p1 p2 p3 -47..50]. Thus a random sample of the numbers -50, -49, -48 is returned instead of something such as
> -42 39 -29 which is one of the samples which GRPfysLUM(-50,50,3) returns.
>
> Derek O'Connor.
- - - - - - - - -
  As you point out, Derek, randomly choosing from a selection of 2, then 3, then 4, etc. forces one to go all the way up to selecting from n. Proceeding in the opposite direction from a selection of n, then n-1, and so forth allows the process to stop after only m steps, which is significant if m is appreciably less than n.

p = a:b;
n = length(p);
for k = n:-1:n-m+1
 q = ceil(k*rand);
 t = p(q);
 p(q) = p(k);
 p(k) = t;
end
p = p(n-m+1:n); % Use the last m elements in p

  In my opinion there is unlikely to be an efficient way that does not use a full n-length vector to randomly choose from with the necessary step "ceil(n*rand)" even though only m are to be chosen.

Roger Stafford

Subject: Random Integers Within Specfic Ranges

From: Roger Stafford

Date: 13 Mar, 2011 20:59:04

Message: 15 of 19

"Roger Stafford" wrote in message <ilgfk4$4s1$1@fred.mathworks.com>...
> As you point out, Derek, randomly choosing from a selection of 2, then 3, then 4, etc. forces one to go all the way up to selecting from n. Proceeding in the opposite direction from a selection of n, then n-1, and so forth allows the process to stop after only m steps, which is significant if m is appreciably less than n.
> ........
- - - - - - - - - -
  Derek, in my previous statement to you there was the tacit implication that the selection needs to use descending sizes to select from in order to work properly. That is actually not the case. It can go in either direction, from a k-index of n down to n-m+1 or else from n-m+1 up to n. Either way all permutations of m out of n numbers are of equal probability in the final m elements of p. This can easily be proved by mathematical induction on m for a fixed value of t=n-m.

  In other words the following works just as well as the previous code:

 p = a:b;
 n = length(p);
 for k = n-m+1:n
  q = ceil(k*rand);
  t = p(q);
  p(q) = p(k);
  p(k) = t;
 end
 p = p(n-m+1:n); % Use the last m elements in p

  It remains true however that starting at k = 1 or 2 will not work for general m out of n unless the iteration is continued up to k = n.

Roger Stafford

Subject: Random Integers Within Specfic Ranges

From: Derek O'Connor

Date: 14 Mar, 2011 09:45:21

Message: 16 of 19

Roger, Bruno,

My apologies. I had forgotten that you were using a descending for-loop. This is what Durstenfeld (1964) used, and Pike's (1965) modification for m < n is exactly the same as Roger's descending loop method. I had not appreciated the importance of the descending
loop until now. It is interesting that the the full n-length vector is needed even though
m << n.

Here is a rejection method that uses O(m) space:
----------------------------------------------
function p = RanSampRej(L,U,m);
p(1:m) = U+1;
n = U-L+1;
for k = 1:m
     r = L + floor(rand*n);
     while member(r,p,k)
            r = L + floor(rand*n);
     end
     p(k) = r;
end

function answer = member(e,v,k)
answer = false;
for i = 1:k
     if v(i) == e
          answer = true;
          return
     end
end
----------------------------------------------

The p(1:m) = U+1 is needed to ensure that member(e,v,k) works correctly. The complexity is at least O(m^2) and because of the while-loop, the running time is random.

This method saves a lot of space when n = U-L+1 is very large, and is reasonably fast when m is small.

Regards,

Derek O'Connor

Subject: Random Integers Within Specfic Ranges

From: Derek O'Connor

Date: 14 Mar, 2011 15:58:05

Message: 17 of 19

Two small tweaks:

Change p(1:m) = U+1 to p = zeros(1,m);

Change while member(r,p,k) to while member(r,p,k-1)

Derek O'Connor

Subject: Random Integers Within Specfic Ranges

From: RogerB .

Date: 14 Mar, 2011 16:28:05

Message: 18 of 19

"Nasser M. Abbasi" <nma@12000.org> wrote in message <ildhbm$lnk$1@speranza.aioe.org>...


No, using randperm in this way wont work. The numbers have different meanings and when I generate a vector with say 1e6 simulations, simulations been the combinations of 5 integers, and I have a (1e6,5) vector and I plan to categorize each row of the vector to asses the simulations.
However I have not looked into the randperm function in detail at the minute and I am sure it will be of use at some stage. Thanks Nasser

Subject: Random Integers Within Specfic Ranges

From: RogerB .

Date: 14 Mar, 2011 16:38:05

Message: 19 of 19

Roger Stafford said

> - - - - - - - - - -
> The following will make fewer calls on 'rand' than 'randperm' and it does not do a sort (though it may be slower nevertheless.) The n-length rows of the output array x will be given non-repeating integers selected randomly from 1:N. We must therefore have n <= N. This is repeated for each of the m rows of x.
>
> x = zeros(m,n);
> p = zeros(1,N);
> for j = 1:m
> p(1:N) = 1:N;
> for k = N:-1:N-n+1
> q = ceil(k*rand);
> x(j,N-k+1) = p(q);
> p(q:k-1) = p(q+1:k);
> end
> end
>
> Roger Stafford


Thank you Roger S. I have just tried your code out and its spot on. Thank you very much!

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