http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272
MATLAB Central Newsreader  Random Integers Within Specfic Ranges
Feed for thread: Random Integers Within Specfic Ranges
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Fri, 11 Mar 2011 15:51:04 +0000
Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824493
RogerB .
Hi,<br>
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:<br>
Generate five numbers between 1 and 20.<br>
Range is between 1 and 20,<br>
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. <br>
So the output matrix could look something like this<br>
1046142<br>
8171661<br>
2191445<br>
71915320<br>
42 20917<br>
18791110<br>
And so on. <br>
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.<br>
How can I close out part of the range for the next number to be generated.<br>
So in the case of the range (120) the rand function generates a number between 01 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 (19) and (1120) and so on?<br>
<br>
Thanks inadvance!

Fri, 11 Mar 2011 16:07:14 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824498
Nasser M. Abbasi
On 3/11/2011 7:51 AM, RogerB . wrote:<br>
> Hi,<br>
> I can generate random integers within a range (say A to B), its no problem. What I want to do<br>
> is generate a series of number one after the other. For example:<br>
> Generate five numbers between 1 and 20.<br>
> Range is between 1 and 20,<br>
> When the first integer is generated the second one cannot be the same as the first one and<br>
> the third one cannot be the same as the first one or second one and so on.<br>
> So the output matrix could look something like this<br>
> 1046142<br>
> 8171661<br>
> 2191445<br>
> 71915320<br>
> 42 20917<br>
> 18791110<br>
> And so on.<br>
> When I use the rand function I can generate the five numbers within the range but<br>
>the numbers can repeat themselves, I want to avoid this.<br>
> How can I close out part of the range for the next number to be generated.<br>
> So in the case of the range (120) the rand function generates a number between 01<br>
> and multiplies it by 20 and rounds it. If the first of the five numbers is 10, how can<br>
>I get the second number to fall, uniformly, in the remaining two ranges (19) and (1120) and so on?<br>
><br>
> Thanks inadvance!<br>
<br>
can you use randperm?<br>
<br>
do randperm(20), then take the first 5 numbers or any 5 will do, since<br>
all random.<br>
<br>
do that again, as many times. randperm will not duplicate numbers<br>
in its result.<br>
<br>
EDU>> randperm(5)<br>
2 3 4 1 5<br>
EDU>> randperm(5)<br>
3 4 5 2 1<br>
EDU>> randperm(5)<br>
4 2 3 1 5<br>
EDU>> randperm(5)<br>
2 3 1 5 4<br>
<br>
<br>
Nasser

Fri, 11 Mar 2011 21:17:07 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824546
Roger Stafford
"RogerB ." wrote in message <ildgd8$dhl$1@fred.mathworks.com>...<br>
> Hi,<br>
> 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:<br>
> Generate five numbers between 1 and 20.<br>
> Range is between 1 and 20,<br>
> 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. <br>
> So the output matrix could look something like this<br>
> 1046142<br>
> 8171661<br>
> 2191445<br>
> 71915320<br>
> 42 20917<br>
> 18791110<br>
> And so on. <br>
> 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.<br>
> How can I close out part of the range for the next number to be generated.<br>
> So in the case of the range (120) the rand function generates a number between 01 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 (19) and (1120) and so on?<br>
> <br>
> Thanks inadvance!<br>
         <br>
The following will make fewer calls on 'rand' than 'randperm' and it does not do a sort (though it may be slower nevertheless.) The nlength rows of the output array x will be given nonrepeating integers selected randomly from 1:N. We must therefore have n <= N. This is repeated for each of the m rows of x.<br>
<br>
x = zeros(m,n);<br>
p = zeros(1,N);<br>
for j = 1:m<br>
p(1:N) = 1:N;<br>
for k = N:1:Nn+1<br>
q = ceil(k*rand);<br>
x(j,Nk+1) = p(q);<br>
p(q:k1) = p(q+1:k);<br>
end<br>
end<br>
<br>
Roger Stafford

Fri, 11 Mar 2011 23:28:05 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824559
Jan Simon
Dear RogerB,<br>
<br>
For small vectors RANDPERM is fine. For larger vectors, the CMex Shuffle can save processing time:<br>
<a href="http://www.mathworks.com/matlabcentral/fileexchange/27076shuffle">http://www.mathworks.com/matlabcentral/fileexchange/27076shuffle</a><br>
<br>
Kind regards, Jan

Sat, 12 Mar 2011 02:22:05 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824568
David Dresden
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.

Sat, 12 Mar 2011 03:47:06 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824576
Roger Stafford
"David Dresden" <liquidnitrogenoverclocking@hushmail.com> wrote in message <ilelcd$b5f$1@fred.mathworks.com>...<br>
> 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.<br>
          <br>
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 <= BA+1.<br>
<br>
x = zeros(m,n);<br>
N = BA+1;<br>
p = zeros(1,N);<br>
for j = 1:m<br>
p(1:N) = A:B;<br>
for k = N:1:Nn+1<br>
q = ceil(k*rand);<br>
x(j,Nk+1) = p(q);<br>
p(q:k1) = p(q+1:k);<br>
end<br>
end<br>
<br>
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.<br>
<br>
Roger Stafford

Sat, 12 Mar 2011 07:15:22 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824590
Bruno Luong
"Roger Stafford" wrote in message <ileqbq$s0e$1@fred.mathworks.com>...<br>
<br>
> <br>
> x = zeros(m,n);<br>
> N = BA+1;<br>
> p = zeros(1,N);<br>
> for j = 1:m<br>
> p(1:N) = A:B;<br>
> for k = N:1:Nn+1<br>
> q = ceil(k*rand);<br>
> x(j,Nk+1) = p(q);<br>
> p(q:k1) = p(q+1:k);<br>
> end<br>
> end<br>
> <br>
> 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.<br>
<br>
Roger, I guess the bigger time spend i your code is in the statement<br>
p(q:k1) = p(q+1:k);<br>
<br>
If the array would be stored as chainlist rather than contiguous, moving the block will cost constant time. Unfortunately Matlab does not offer such data structure.<br>
<br>
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.<br>
<br>
Bruno

Sat, 12 Mar 2011 08:59:05 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824599
Roger Stafford
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ilf6ia$r0f$1@fred.mathworks.com>...<br>
> "Roger Stafford" wrote in message <ileqbq$s0e$1@fred.mathworks.com>...<br>
> .......<br>
> > p(q:k1) = p(q+1:k);<br>
> > ......<br>
> <br>
> Roger, I guess the bigger time spend i your code is in the statement<br>
> p(q:k1) = p(q+1:k);<br>
> <br>
> If the array would be stored as chainlist rather than contiguous, moving the block will cost constant time. Unfortunately Matlab does not offer such data structure.<br>
> <br>
> 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.<br>
> <br>
> Bruno<br>
         <br>
Yes, I should have used this instead:<br>
<br>
p(q) = p(k);<br>
<br>
That would work just as well and it would change it from O(N^2) to O(N).<br>
<br>
Roger Stafford

Sat, 12 Mar 2011 09:25:04 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824601
Bruno Luong
"Roger Stafford" wrote in message <ilfckp$rs1$1@fred.mathworks.com>...<br>
<br>
> Yes, I should have used this instead:<br>
> <br>
> p(q) = p(k);<br>
> <br>
> That would work just as well and it would change it from O(N^2) to O(N).<br>
> <br>
> Roger Stafford<br>
<br>
The small change makes the algo become much better. Thanks.<br>
<br>
Bruno

Sat, 12 Mar 2011 14:15:07 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824619
Derek O'Connor
"RogerB ." wrote in message <ildgd8$dhl$1@fred.mathworks.com>...<br>
> Hi,<br>
> 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:<br>
> Generate five numbers between 1 and 20.<br>
> Range is between 1 and 20,<br>
> 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. <br>
snip <br>
<br>
This is a minor variation on Durstenfeld's implementation of the FisherYates 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.<br>
<br>
<br>
function p = GRPfysLUM(L,U,m);<br>
n = UL+1;<br>
p = L:U; % Start with complete range and then randomly shuffle these integers<br>
for k = 2:n<br>
r = ceil(rand*k);<br>
t = p(k);<br>
p(k) = p(r);<br>
p(r) = t;<br>
end<br>
p = p(1:m); % return the first m as the sample.<br>
<br>
<br>
<br>
The complexity of this function is O(n).<br>
<br>
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 forloop takes n1 steps.<br>
<br>
Is there an optimum algorithm for all m <= n or otherwise?<br>
<br>
Derek O'Connor.

Sat, 12 Mar 2011 14:53:04 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824621
Bruno Luong
"Derek O'Connor" wrote in message <ilfv5b$6pa$1@fred.mathworks.com>...<br>
<br>
> <br>
> 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 forloop takes n1 steps.<br>
> <br>
<br>
Storing full p seems to be unavoidable in Roger's method.<br>
The point (2) is not a point, just iterate m time then stop.<br>
<br>
Bruno

Sat, 12 Mar 2011 17:36:04 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824645
Derek O'Connor
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ilg1cg$r6q$1@fred.mathworks.com>...<br>
> "Derek O'Connor" wrote in message <ilfv5b$6pa$1@fred.mathworks.com>...<br>
> <br>
> > <br>
> > 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 forloop takes n1 steps.<br>
> > <br>
> <br>
> Storing full p seems to be unavoidable in Roger's method.<br>
> The point (2) is not a point, just iterate m time then stop.<br>
> <br>
> Bruno<br>
<br>
Bruno,<br>
<br>
Point (2) is a point. <br>
<br>
for k = 2:m does not work. Note the first statement in the for kloop: r = ceil(rand*k);<br>
<br>
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 <br>
42 39 29 which is one of the samples which GRPfysLUM(50,50,3) returns.<br>
<br>
Derek O'Connor.

Sat, 12 Mar 2011 18:52:07 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824651
Bruno Luong
Derek wrote:<br>
> <br>
> Point (2) is a point. <br>
> <br>
<br>
Not to me:<br>
<br>
x = zeros(1,m);<br>
p = 1:N;<br>
for k = N:1:Nm+1<br>
q = ceil(k*rand);<br>
x(Nk+1) = p(q);<br>
p(q) = p(k);<br>
end<br>
<br>
% Bruno

Sat, 12 Mar 2011 18:56:04 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824652
Roger Stafford
"Derek O'Connor" wrote in message <ilgau4$5hb$1@fred.mathworks.com>...<br>
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ilg1cg$r6q$1@fred.mathworks.com>...<br>
> > "Derek O'Connor" wrote in message <ilfv5b$6pa$1@fred.mathworks.com>...<br>
> > > 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 forloop takes n1 steps.<br>
> > <br>
> > Storing full p seems to be unavoidable in Roger's method.<br>
> > The point (2) is not a point, just iterate m time then stop.<br>
> > <br>
> > Bruno<br>
> <br>
> Bruno,<br>
> <br>
> Point (2) is a point. <br>
> <br>
> for k = 2:m does not work. Note the first statement in the for kloop: r = ceil(rand*k);<br>
> <br>
> 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 <br>
> 42 39 29 which is one of the samples which GRPfysLUM(50,50,3) returns.<br>
> <br>
> Derek O'Connor.<br>
        <br>
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 n1, and so forth allows the process to stop after only m steps, which is significant if m is appreciably less than n.<br>
<br>
p = a:b;<br>
n = length(p);<br>
for k = n:1:nm+1<br>
q = ceil(k*rand);<br>
t = p(q);<br>
p(q) = p(k);<br>
p(k) = t;<br>
end<br>
p = p(nm+1:n); % Use the last m elements in p<br>
<br>
In my opinion there is unlikely to be an efficient way that does not use a full nlength vector to randomly choose from with the necessary step "ceil(n*rand)" even though only m are to be chosen.<br>
<br>
Roger Stafford

Sun, 13 Mar 2011 20:59:04 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824812
Roger Stafford
"Roger Stafford" wrote in message <ilgfk4$4s1$1@fred.mathworks.com>...<br>
> 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 n1, and so forth allows the process to stop after only m steps, which is significant if m is appreciably less than n.<br>
> ........<br>
         <br>
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 kindex of n down to nm+1 or else from nm+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=nm.<br>
<br>
In other words the following works just as well as the previous code:<br>
<br>
p = a:b;<br>
n = length(p);<br>
for k = nm+1:n<br>
q = ceil(k*rand);<br>
t = p(q);<br>
p(q) = p(k);<br>
p(k) = t;<br>
end<br>
p = p(nm+1:n); % Use the last m elements in p<br>
<br>
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.<br>
<br>
Roger Stafford

Mon, 14 Mar 2011 09:45:21 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824883
Derek O'Connor
Roger, Bruno,<br>
<br>
My apologies. I had forgotten that you were using a descending forloop. 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<br>
loop until now. It is interesting that the the full nlength vector is needed even though <br>
m << n.<br>
<br>
Here is a rejection method that uses O(m) space:<br>
<br>
function p = RanSampRej(L,U,m);<br>
p(1:m) = U+1;<br>
n = UL+1;<br>
for k = 1:m<br>
r = L + floor(rand*n);<br>
while member(r,p,k)<br>
r = L + floor(rand*n);<br>
end<br>
p(k) = r;<br>
end<br>
<br>
function answer = member(e,v,k)<br>
answer = false;<br>
for i = 1:k<br>
if v(i) == e<br>
answer = true;<br>
return<br>
end<br>
end<br>
<br>
<br>
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 whileloop, the running time is random.<br>
<br>
This method saves a lot of space when n = UL+1 is very large, and is reasonably fast when m is small.<br>
<br>
Regards,<br>
<br>
Derek O'Connor

Mon, 14 Mar 2011 15:58:05 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824972
Derek O'Connor
Two small tweaks:<br>
<br>
Change p(1:m) = U+1 to p = zeros(1,m);<br>
<br>
Change while member(r,p,k) to while member(r,p,k1)<br>
<br>
Derek O'Connor

Mon, 14 Mar 2011 16:28:05 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824978
RogerB .
"Nasser M. Abbasi" <nma@12000.org> wrote in message <ildhbm$lnk$1@speranza.aioe.org>...<br>
<br>
<br>
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.<br>
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

Mon, 14 Mar 2011 16:38:05 +0000
Re: Random Integers Within Specfic Ranges
http://www.mathworks.com/matlabcentral/newsreader/view_thread/304272#824982
RogerB .
Roger Stafford said<br>
<br>
>          <br>
> The following will make fewer calls on 'rand' than 'randperm' and it does not do a sort (though it may be slower nevertheless.) The nlength rows of the output array x will be given nonrepeating integers selected randomly from 1:N. We must therefore have n <= N. This is repeated for each of the m rows of x.<br>
> <br>
> x = zeros(m,n);<br>
> p = zeros(1,N);<br>
> for j = 1:m<br>
> p(1:N) = 1:N;<br>
> for k = N:1:Nn+1<br>
> q = ceil(k*rand);<br>
> x(j,Nk+1) = p(q);<br>
> p(q:k1) = p(q+1:k);<br>
> end<br>
> end<br>
> <br>
> Roger Stafford<br>
<br>
<br>
Thank you Roger S. I have just tried your code out and its spot on. Thank you very much!