Recent

Author Topic: How to efficiently generate a list of random integers within a range?  (Read 12973 times)

WayneSherman

  • Jr. Member
  • **
  • Posts: 70

Thaddy

  • Hero Member
  • *****
  • Posts: 10450
Re: How to efficiently generate a list of random integers within a range?
« Reply #31 on: February 12, 2020, 06:40:12 pm »
For your Sattolo implementation, you have an error that requires an extra loop iteration.  When i = 0 then j = 0, so you are swapping a[0] with a[0].  Therefore:
Line 12:    while i > 0 do
should be
Line 12:    while i > 1 do
That is not true. You will introduce a fixed member in that case, so it is no longer random over the population.
I also think you do not understand that Sattolo takes one less iteration compared to Fisher-Yates....
Unless I am proven wrong, I am not likely to adapt the code: It is an implementation of the standard algorithm.
When you ask a question that is actually answered in the documentation, you are either lazy or a moron.

WayneSherman

  • Jr. Member
  • **
  • Posts: 70
Re: How to efficiently generate a list of random integers within a range?
« Reply #32 on: February 12, 2020, 11:34:12 pm »
Think about the last iteration when when i = 1

Code: Pascal  [Select][+][-]
  1. while i > 0 do                    //i = 1, 1>0 is true so lets enter the while loop
  2. begin
  3.     dec(i);                       //i = 0 after this line
  4.     j :=randomrange(Low(a),i);    //j = randomrange(0,0) = 0
  5.     t:=a[i];a[i]:=a[j];a[j]:=t;   //since both i=0 and j=0 they both reference the same element and swap doesn't do anything.  so we didn't have to make this iteration
  6.     write(a[i]:4);
  7. end;
« Last Edit: February 12, 2020, 11:36:06 pm by WayneSherman »


 

TinyPortal © 2005-2018