OpenEuphoria

Re: question unsort(x)

• Posted by Fernando Bauer <fmbauer at hotmail.co?> Aug 07, 2007
• 538 views

Hi Ricardo,

I downloaded your great genfunc.e library and was studying your functions
RandomPermutation() and Scramble(). I think
they are using a biased algorithm because the value passed to rand() function
("len") is constant. Thus, the code can potentially
generate (len^len) permutations but many of them will be equal (by pigeonhole
principle), as we have only (len!) possible permutations.
Maybe for Salix, this doesn't matter, but for statistics and cryptography an
unbiased Knuth Shuffle is important.

Hi Salix. Searching the EUforum, there is a code to shuffle by Gabriel Boehme:
http://www.openeuphoria.org/cgi-bin/esearch.exu?thread=1&fromMonth=B&fromYear=4&toMonth=1&toYear=5&keywords=%22The+%22industry+standard%22+shuffle+algorithm+in+Euphoria%22

global function shuffle(sequence s)
-- randomly shuffle the elements of a sequence
-- written by Gabriel Boehme
--    based Jiri Babor's Euphoria interpretation of the "uniformly random"
--    1963 shuffle algorithm written by L.E. Moses and R.V. Oakford
integer r
object temp
   for i = length(s) to 2 by -1 do
      r = rand(i)
      temp = s[r]
      s[r] = s[i]
      s[i] = temp
   end for
   return s
end function

For more interesting information:
http://en.wikipedia.org/wiki/Shuffle#Shuffling_algorithms

Regards,
   Fernando