Really fricken simple Pseudo-Random traversal of a Set

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • Really fricken simple Pseudo-Random traversal of a Set

      I have a really simple method to traverse a known set of items randomly only once. It may or may not require a more memory than the method described in the book (depends on the size of the array) but it's definately faster (except of the initial creation).

      The method is simple, you stick all of the elements you want into an array (for speed purposes, most likely an array of pointers). Next you loop through each element of the array and swap it's value with an other random element of the array. Voila! Everything will now be in some crazy mixed up order. Now, instead of doing some fancy calculations you can just grab each number/pointer sequentially from the array.

    • RE: Really fricken simple Pseudo-Random traversal of a Set

      That's not a bad solution if you don't mind rearranging the data set, or making a copy of the data set.

      And as you said, your solution is really simple! I like that, because the PrimeSearch algorithm makes my head hurt to look at it...

      I wonder if anyone has done any work that can tell you how many swaps you need to do in a set of a given size to adequately ensure a random distribution - I know that you'd have to do multiple passes.

      If too many passes were required, the initialization time might be onorous for large sets.
      Mr.Mike
      Author, Programmer, Brewer, Patriot

    • hm.. if those changes dont matter, how about storing the size of the array, picking a random value, then change its position with the last value and reducing the size by one.

      something along

      int i=rand()%size; //or a better one
      T x=array;
      //do whatever
      array[i]=array[--size];
      array[size]=x;

      problem i see is that with the changed array the same random numbers would still return different values. if you can afford to copy the whole array (maybe its just pointers), then at least you can save yourself the trouble of copying the used value to the end. if you pre allocate the tmp array that should even be faster, as many small copys are replaced by one memcpy.

      memcpy(tmparray, array, sizeof(array) );
      int i=rand()%size; //or a better one
      //do whatever
      array[i]=array[--size];

      but maybe im completely missing the point what it's all about ,-)