COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Processing numbers in random order

• Email
• Follow

```Given N, where N is an integer > 0, process the numbers 1-N in random order.

The best I can come up with is:

List = ''			/* Generate a list		*/
Do I = 1 to N			/* Of numbers from 1-N		*/
List = list I			/* Add number to list		*/
End
Do while list <> ''		/* Process list			*/
I = random(1,words(list))	/* Chose random number		*/
J = word(list,i)		/* Get original number		*/
List = delword(list,I,1)	/* Stop it being used again	*/
... Process item "J"		/* Do something with item J	*/
End

This seems a lot of code for a relatively simple task. It also runs
inefficiently if N is large, because of the constant increasing in the
length of the variable "list" in the first loop.

How would you do it?

--
Steve Swift
http://www.swiftys.org.uk/swifty.html
http://www.ringers.org.uk
```
 0

See related articles to this posting

```"Steve Swift" <Steve.J.Swift@gmail.com> wrote in message
news:475f5b84@news.greennet.net...
> Given N, where N is an integer > 0, process the numbers 1-N in random
> order.
>
> The best I can come up with is:
>
> List = '' /* Generate a list */
> Do I = 1 to N /* Of numbers from 1-N */
>   List = list I /* Add number to list */
>   End
> Do while list <> '' /* Process list */
>   I = random(1,words(list)) /* Chose random number */
>   J = word(list,i) /* Get original number */
>   List = delword(list,I,1) /* Stop it being used again */
>   ... Process item "J" /* Do something with item J */
>   End
>
> This seems a lot of code for a relatively simple task. It also runs
> inefficiently if N is large, because of the constant increasing in the
> length of the variable "list" in the first loop.
>
> How would you do it?
>
> --
> Steve Swift
> http://www.swiftys.org.uk/swifty.html
> http://www.ringers.org.uk

I did similar a long time ago.... something like this.
/* */
max = 20 /* say */
random. = randomise(max)

::method randomise
use arg max
sequence = 0
random.0 = max
j = 0
do i = 1 to max
number = random(1, max)
if self~testForDups(number, sequence) = 0 then do
i = i-1
iterate
end
else do
sequence = sequence number
j = j+1
random.j = number
end
end
return random.

::method testForDups
use arg number, sequence
do until used = ''
parse var sequence used sequence
if number = used then return 0
end
return number

Phil
----

```
 0

```In Message-ID:<475f5b84@news.greennet.net>,
Steve Swift <Steve.J.Swift@gmail.com> wrote:

>Given N, where N is an integer > 0, process the numbers 1-N in random order.
<snip>
>How would you do it?

When in doubt, refer to Knuth's Seminumerical Algorithms.
Here's my code based on his shuffling algorith on P. 125:

<code>
max = 30

do i = 1 to max
nums.i = i
end

do i = max to 1 by -1
j = random(1,i)

/* swap nums.j and nums.i */
x = nums.i
nums.i = nums.j
nums.j = x

end

/* now use them */
do i = 1 to max
say right(i,2) ' ' right(nums.i,2)
end
</code>

The built-in RANDOM function requires that the range be no
greater than 100000 (Regina REXX on Windows).  I tested with a
table of 100000, and my timing was:
Time to fill table was     4.750
Time to shuffle table was 18.578

With only 30000, timing was:
Time to fill table was     0.360
Time to shuffle table was  1.312

(Needless to say, when testing with large numbers, I didn't
use the SAY loop.  I also added instructions to get the timings.)

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```Phil wrote:
> I did similar a long time ago.... something like this.

I've also used a similar mechanism to yours; picking numbers at random,
and ignoring them if I've used them before:

Max = 20
Seen. = 0
Do max
Do until \seen.N
N = random(1,max)
End
Seen.N = 1
Say N
End

The problem with this is the way it slows down as "Max" increases,
hunting for the last numbers.

I can see myself running a few benchmarks!

--
Steve Swift
http://www.swiftys.org.uk/swifty.html
http://www.ringers.org.uk
```
 0

```In Message-ID:<475f5b84@news.greennet.net>,
Steve Swift <Steve.J.Swift@gmail.com> wrote:

>Given N, where N is an integer > 0, process the numbers 1-N in random order.
>
>The best I can come up with is:
<snip>
>How would you do it?

Here's an improvement over my previous code, followed by
timings:

<code>
/*REXX exec */

arg max
if \ datatype(max,"N") then max = 1000
t0 = time('r')

do i = max to 1 by -1
if \ datatype(nums.i,'N') then nums.i = i
j = random(1,i)
if datatype(nums.j,'N') then
do
x = nums.i
nums.i = nums.j
nums.j = x
end
else
do
nums.j = nums.i
nums.i = j
end

end
t1 = time('r')
say 'Time to shuffle table was' format(t1,,3)

do i = 1 to max
x = nums.i
end
t2 = time('r')
say 'Time to use the table was' format(t2,,3)

say 'Total time was' format(t1+t2,,3)

exit 0

</code>

On my system, here are timings:
MAX      Yours     Mine
1000     .047     .000
5000    1.328     .047
10000    5.547     .188
30000   66.891    1.625

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```| Arthur T. wrote:
|> Steve Swift wrote:
|> Given N, where N is an integer > 0, process the numbers 1-N in random order.
|>
|> The best I can come up with is:
<snip>
|> How would you do it?

|     Here's an improvement over my previous code, followed by
| timings:
|
| <code>
| /*REXX exec */
|
|  arg max
|  if \ datatype(max,"N") then max = 1000
|  t0 = time('r')
|
|  do i = max to 1 by -1
|    if \ datatype(nums.i,'N') then nums.i = i
|    j = random(1,i)
|    if datatype(nums.j,'N') then
|      do
|        x = nums.i
|        nums.i = nums.j
|        nums.j = x
|      end
|    else
|      do
|        nums.j = nums.i
|        nums.i = j
|      end
|
|  end
|  t1 = time('r')
|  say 'Time to shuffle table was' format(t1,,3)
|
|  do i = 1 to max
|    x = nums.i
|  end
|  t2 = time('r')
|  say 'Time to use the table was' format(t2,,3)
|
|  say 'Total time was' format(t1+t2,,3)
|
|  exit 0
|
| </code>
|
|     On my system, here are timings:
| MAX      Yours     Mine
| 1000     .047     .000
| 5000    1.328     .047
| 10000    5.547     .188
| 30000   66.891    1.625

I tweaked the code a bit and got about a 10% improvement
in execution speed:

================================================================
/*REXX exec*/  arg max .;  if \datatype(max,'N') then max=1000
call time 'R'
nums.=-1

do i=max to 1 by -1
if nums.i<0 then nums.i=i
j=random(1,i)
if nums.j>=0 then parse value nums.i nums.j with nums.j nums.i
else parse value nums.j nums.i with nums.i j
end

t1=time('r')
say 'Time to shuffle table was' format(t1,,3)

do i=1 to max
x=nums.i
end

t2=time('r')
say 'Time to use the table was' format(t2,,3)
say 'Total time was' format(t1+t2,,3)
================================================================
_______________________________________________________Gerard S.

```
 0

```In Message-ID:<475ebdc4\$1@news.702com.net>,
"Gerard Schildberger" <Gerard46@rrt.net> wrote (and I greatly
snipped):

>I tweaked the code a bit and got about a 10% improvement
>in execution speed:
>
>nums.=-1

Checking a variable for a value is probably much more
efficient than my checking for numeric.

>  if nums.j>=0 then parse value nums.i nums.j with nums.j nums.i
>               else parse value nums.j nums.i with nums.i j

It's not often I spot a mistake in your code.  That 2nd line
should be
else parse value      j nums.i with nums.i nums.j
(Spaces left in to highlight the changes.)

And that harkens back to an old thread (here or elsewhere) on
the best way to swap the values of two variables.

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```| Arthur T. wrote:
|> Gerard Schildberger wrote: (and I greatly snipped):
|> I tweaked the code a bit and got about a 10% improvement
|> in execution speed:
|>
|> nums.=-1

|     Checking a variable for a value is probably much more
| efficient than my checking for numeric.

|>  if nums.j>=0 then parse value nums.i nums.j with nums.j nums.i
|>               else parse value nums.j nums.i with nums.i j

|     It's not often I spot a mistake in your code.  That 2nd line
| should be
|                else parse value      j nums.i with nums.i nums.j
| (Spaces left in to highlight the changes.)

Yuppers, my bad;  I was in too much of a hurry to go and eat
breakfast.   Eat first, then code.  _________________Gerard S.

|     And that harkens back to an old thread (here or elsewhere) on
| the best way to swap the values of two variables.

```
 0

```In Message-ID:<475ed293\$1@news.702com.net>,
"Gerard Schildberger" <Gerard46@rrt.net> wrote:

> I was in too much of a hurry to go and eat
>breakfast.   Eat first, then code.

you reverse that order:

1.  You think about food instead of code, and you make mistakes.

2.  You *don't* think about food.  You get immersed in coding.
Several hours later you notice that you're famished.  You have
barely the energy to get to the kitchen, at which point you eat
anything which takes zero preparation time.

Er, um, theoretically, that is.  Not that I'd know about it,
myself.

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```On Dec 11, 4:27 pm, Arthur T. <art...@munged.invalid> wrote:
> In Message-ID:<475f5...@news.greennet.net>,
>
>
>
> Steve Swift <Steve.J.Sw...@gmail.com> wrote:
> >Given N, where N is an integer > 0, process the numbers 1-N in random order.
>  <snip>
> >How would you do it?
>
>      When in doubt, refer to Knuth's Seminumerical Algorithms.
> Here's my code based on his shuffling algorith on P. 125:
>
>  <code>
>   max = 30
>
>   do i = 1 to max
>     nums.i = i
>   end
>
>   do i = max to 1 by -1
>     j = random(1,i)
>
>     /* swap nums.j and nums.i */
>     x = nums.i
>     nums.i = nums.j
>     nums.j = x
>
>   end
>
>   /* now use them */
>   do i = 1 to max
>     say right(i,2) ' ' right(nums.i,2)
>   end
>  </code>
>
>      The built-in RANDOM function requires that the range be no
> greater than 100000 (Regina REXX on Windows).  I tested with a
> table of 100000, and my timing was:
> Time to fill table was     4.750
> Time to shuffle table was 18.578
>
>      With only 30000, timing was:
> Time to fill table was     0.360
> Time to shuffle table was  1.312
>
>      (Needless to say, when testing with large numbers, I didn't
> use the SAY loop.  I also added instructions to get the timings.)
>
> --
> Arthur T. - ar23hur "at" intergate "dot" com
> Looking for a z/OS (IBM mainframe) systems programmer position

That's a gem of an algorithm.

I thought Steve had a good one too, but this is far better of course.
Interesting how Steve had a hunch that there may be a better way...

a minor note: there is no real need for a separate loop to process the
random numbers (the 'now use them' loop), because all that is required
is a random processing of all numbers (so the random number at max may
be processed first, and so on...)

and re your later comment about swapping 2 variables p, q, you may be
aware that REXX provides another good way: q= value("p", q)

Regards
HS

```
 0

```Steve Swift wrote:
> Given N, where N is an integer > 0, process the numbers 1-N in random
> order.

Thanks for all the replies here.  I decided to write a benchmark between
Arthur's code and my code. I knew that my code was doomed as "max"
increases; the effect of continually lengthening a variable. However,
there was no value of max where my code won. The extreme case occurred
when I accidentally changed "max" to 10000. My code took 342 seconds
(125 iterations) and Arthur's 11 seconds (125 iterations)

I'm so pleased with the outcome that I'm going to add a new function to
my subroutine library which returns a list of numbers from 1 to max in
random order. The hard part comes last: finding a good name for such a
function. :-)

--
Steve Swift
http://www.swiftys.org.uk/swifty.html
http://www.ringers.org.uk
```
 0

```In <4763df39@news.greennet.net>, on 12/14/2007
at 02:21 PM, Steve Swift <Steve.J.Swift@gmail.com> said:

>I'm so pleased with the outcome that I'm going to add a new function to
>my subroutine library which returns a list of numbers from 1 to max in
>random order. The hard part comes last: finding a good name for such a
>function. :-)

APL has had this function since the beginning as the dyadic use of a ? as
a function.  It is referred to as the "deal" function, I suspect because
one application would be in dealing a deck of cards.

-- Dave
-----------------------------------------------------------
dhdurgee<at>verizon<dot>net
-----------------------------------------------------------

```
 0

```In
hs <hrmndrsingh@gmail.com> wrote:

>That's a gem of an algorithm.

I steal from the best.  It's hard to better Knuth.

>a minor note: there is no real need for a separate loop to process the
>random numbers (the 'now use them' loop), because all that is required
>is a random processing of all numbers (so the random number at max may
>be processed first, and so on...)

Good point.  So the timings would actually be better.

>and re your later comment about swapping 2 variables p, q, you may be
>aware that REXX provides another good way: q= value("p", q)

I don't remember that coming up in the thread.  I've looked
it up, and I'll have to remember it.  If I use it, I'll also want
to comment it, as it's not something I'd normally remember.

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```In Message-ID:<4763df39@news.greennet.net>,
Steve Swift <Steve.J.Swift@gmail.com> wrote:

>I'm so pleased with the outcome that I'm going to add a new function to
>my subroutine library which returns a list of numbers from 1 to max in
>random order. The hard part comes last: finding a good name for such a
>function. :-)

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```My initial offering was limp...
I found long ago that stems and parse are both wonderful but slow.

I dabled with variations on my first go by holding the misses (duplicate
randoms) in an array but to cut to the chase there appears to be no better
way to get there than has already been posted here.

What I did though, is to substitute an array for the stem and eliminate the
parse in the process.  Here it is with timings run on IBM Object Rexx 213.

Here are the 2 methods I used:

::method shuffle1 --mine
use arg max
array = .array~new(max)
do i = 1 to max
array[i] = i
end
do i = max to 2 by -1
j=random(1,i)
val1 = array[i]
val2 = array[j]
array[i] = val2
array[j] = val1
end
return array

::method shuffle2 --yours
use arg max
nums. = -1
do i = max to 1 by -1
if nums.i < 0 then nums.i=i
j=random(1,i)
if nums.j >= 0 then parse value nums.i nums.j with nums.j nums.i
else parse value j nums.i with nums.i nums.j
end
nums.0 = max
return nums.

And here are the times which include reading the results:
Max        Yours     Mine
1000    0.062    0.000
5000    0.188    0.062
10000    0.328    0.078
30000    0.687    0.313
50000    1.156    0.407
100000    2.579    0.641

Phil
----

"Gerard Schildberger" <Gerard46@rrt.net> wrote in message
news:475ebdc4\$1@news.702com.net...
>| Arthur T. wrote:
> |> Steve Swift wrote:
> |> Given N, where N is an integer > 0, process the numbers 1-N in random
> order.
> |>
> |> The best I can come up with is:
> <snip>
> |> How would you do it?
>
> |     Here's an improvement over my previous code, followed by
> | timings:
> |
> | <code>
> | /*REXX exec */
> |
> |  arg max
> |  if \ datatype(max,"N") then max = 1000
> |  t0 = time('r')
> |
> |  do i = max to 1 by -1
> |    if \ datatype(nums.i,'N') then nums.i = i
> |    j = random(1,i)
> |    if datatype(nums.j,'N') then
> |      do
> |        x = nums.i
> |        nums.i = nums.j
> |        nums.j = x
> |      end
> |    else
> |      do
> |        nums.j = nums.i
> |        nums.i = j
> |      end
> |
> |  end
> |  t1 = time('r')
> |  say 'Time to shuffle table was' format(t1,,3)
> |
> |  do i = 1 to max
> |    x = nums.i
> |  end
> |  t2 = time('r')
> |  say 'Time to use the table was' format(t2,,3)
> |
> |  say 'Total time was' format(t1+t2,,3)
> |
> |  exit 0
> |
> | </code>
> |
> |     On my system, here are timings:
> | MAX      Yours     Mine
> | 1000     .047     .000
> | 5000    1.328     .047
> | 10000    5.547     .188
> | 30000   66.891    1.625
>
>
>
> I tweaked the code a bit and got about a 10% improvement
> in execution speed:
>
> ================================================================
> /*REXX exec*/  arg max .;  if \datatype(max,'N') then max=1000
> call time 'R'
> nums.=-1
>
>  do i=max to 1 by -1
>  if nums.i<0 then nums.i=i
>  j=random(1,i)
>  if nums.j>=0 then parse value nums.i nums.j with nums.j nums.i
>               else parse value nums.j nums.i with nums.i j
>  end
>
>  t1=time('r')
>  say 'Time to shuffle table was' format(t1,,3)
>
>    do i=1 to max
>    x=nums.i
>    end
>
>  t2=time('r')
>  say 'Time to use the table was' format(t2,,3)
>  say 'Total time was' format(t1+t2,,3)
> ================================================================
> _______________________________________________________Gerard S.
>
>
>
>

```
 0

```I made changes to:
1) Not include the value of index i in the random number search - this will
result in only replacing itself.
2) Stop half way on the assumption that if the top half of the array has
been toggled then the bottom half must also be done.
3) Reduce the reads of the array from 2 to 1

I may have some of this wrong and in any case the changes made little
difference to the timing.
Phil
----

::method shuffle1
use arg max
array = .array~new(max)
do i = 1 to max
array[i] = i
end
do i = max to max/2 by -1
j = random(1,i-1)
vali = array[i]
array[i] = array[j]
array[j] = vali
end
return array

```
 0

```In Message-ID:<47684e61\$0\$8430\$afc38c87@news.optusnet.com.au>,
"Phil" <obrienpw@optusnet.com.au> wrote:

>1) Not include the value of index i in the random number search - this will
>result in only replacing itself.

Making it less random because it's impossible to have a
number in the top half which doesn't move.

>2) Stop half way on the assumption that if the top half of the array has
>been toggled then the bottom half must also be done.

Making it *much* less random by greatly increasing the chance
that a number in the bottom half won't move.

#1 seemed likely on inspection and was confirmed by printing
the tables.  I expected some problem with #2 and printing the
output showed the above problem.

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```Maybe #2 was not thought through... but why is #1 incorrect?

Is it not possible to be at index 10 and request a random number from 1-10
and end up swapping 10 with 10?

Phil
----

"Arthur T." <arthur@munged.invalid> wrote in message
news:sclgm393hhvu5knqq34gjr22287s9pedaa@4ax.com...
> In Message-ID:<47684e61\$0\$8430\$afc38c87@news.optusnet.com.au>,
> "Phil" <obrienpw@optusnet.com.au> wrote:
>
>>1) Not include the value of index i in the random number search - this
>>will
>>result in only replacing itself.
>
>     Making it less random because it's impossible to have a
> number in the top half which doesn't move.
>
>>2) Stop half way on the assumption that if the top half of the array has
>>been toggled then the bottom half must also be done.
>
>     Making it *much* less random by greatly increasing the chance
> that a number in the bottom half won't move.
>
>     #1 seemed likely on inspection and was confirmed by printing
> the tables.  I expected some problem with #2 and printing the
> output showed the above problem.
>
> --
> Arthur T. - ar23hur "at" intergate "dot" com
> Looking for a z/OS (IBM mainframe) systems programmer position

```
 0

```Phil wrote:
> Is it not possible to be at index 10 and request a random number from 1-10
> and end up swapping 10 with 10?

Yes, it is--possible, and correct.  The optimization you want is not to
remove i from the search, but just to skip the swap if j=i.

�R
```
 0

```In Message-ID:<47685e04\$0\$5200\$afc38c87@news.optusnet.com.au>,
"Phil" <obrienpw@optusnet.com.au> wrote:

>Maybe #2 was not thought through... but why is #1 incorrect?
>
>Is it not possible to be at index 10 and request a random number from 1-10
>and end up swapping 10 with 10?

Yes it should be.  However, your change limited it to
swapping with a random number (actually a random location) from
1-9, not 1-10.

Or, are you suggesting that swapping 10 with 10 should never
happen?  In that case, as I said, you'll *never* have location 10
have value 10.  So, if you had to guess what number was in
location 10, you'd have an 11+% chance of being right instead of
only a 10% chance.  Similarly, a game of War between an unshuffled
deck and one shuffled with your #1 would never have a War during
the first run-through.

You could check to see if you're swapping a location with
itself and do nothing.  I suspect that it wouldn't speed things up
because you'd do the check many more times than you'd prevent a
"do nothing" swap.

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```Thanks, Glenn and Arthur... I see the light!

Give me this though... there is no need to do the last swap of location 1
with location 1 so I only need to count down to 2.

Times again:
Max         Stem     Array
1000    0.032    0.000
5000    0.186    0.032
10000    0.359    0.094
30000    0.641    0.281
50000    1.187    0.390
100000    2.626    0.782

Enjoyed the discussion... thanks Steve.

Phil
----

```
 0

```In Message-ID:<47687057\$0\$25392\$afc38c87@news.optusnet.com.au>,
"Phil" <obrienpw@optusnet.com.au> wrote:

>Thanks, Glenn and Arthur... I see the light!
>
>Give me this though... there is no need to do the last swap of location 1
>with location 1 so I only need to count down to 2.

That sounds right.  OTOH, anything dealing with random
numbers is as hard to get right as an encryption algorithm.  Since
this algorithm comes from a trusted source (Knuth), I'd tend to
leave it matching his method as close as possible.  After all,
it's only once through the loop.

>Times again:
>Max         Stem     Array
>    1000    0.032    0.000
>    5000    0.186    0.032
>  10000    0.359    0.094
>  30000    0.641    0.281
>  50000    1.187    0.390
>100000    2.626    0.782

Since I'm using a classic REXX rather than oo, I didn't have
the array option.  But, this is good info for those that do run
oo, and for me when or if I go oo.

>Enjoyed the discussion... thanks Steve.

As I said, it's very easy to make mistakes with random
numbers.  (I forget who said, "Random numbers are too important to
be left to chance.")

--
Arthur T. - ar23hur "at" intergate "dot" com
Looking for a z/OS (IBM mainframe) systems programmer position
```
 0

```Glenn Knickerbocker wrote:
> Yes, it is--possible, and correct.  The optimization you want is not to
> remove i from the search, but just to skip the swap if j=i.

I end up agonising whether the "if" statement will consume more CPU than
the redundant swap. http://www.swiftys.org.uk/wiz?267

--
Steve Swift
http://www.swiftys.org.uk/swifty.html
http://www.ringers.org.uk
```
 0

```One approach, if you want 0..n-1 in some pseudorandom order, is to
find the smallest power of two bigger or equal to n (call it m),
initialize x to some seed, and do (sorry, C not REXX)
for (i=0; i<n; ++i) {
do {
y = x = (x + 0xdeadbeef) & (m-1);
y = (y + (y<<5)) & (m-1);
y = y ^ (y>>3);
} while (y >= n);
printf("%d", x);
}
That reports y=0..n-1 in some pseudorandom order then repeats.
Duplicating those two lines with shifts increases the
pseudorandomness, and the optimal shift amounts vary with m.  Key to
this working is that those two shift lines are permutations of
0..m-1.  Often the right thing to do is not have any shift lines at
all.

This approach doesn't require an array.
```
 0

23 Replies
179 Views

Similar Articles

12/6/2013 12:25:42 AM
[PageSpeed]