Thread Subject:

Random Integers Within Specfic Ranges

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!

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

"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

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

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 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

"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

"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

"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

"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.

"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 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.

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

"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

"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

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

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

"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

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!