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

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

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

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

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

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

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

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

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.

     Always good advice.  Either of two bad things can happen when
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

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

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

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

In
Message-ID:<b060371d-d1db-4f4e-a731-18bd7a01266a@i12g2000prf.googlegroups.com>,
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

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. :-)

     How about "shuffle"?

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

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

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

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

>I made changes to:
>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

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:
>
>>I made changes to:
>>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 

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

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

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

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

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

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.