1. question unsort(x)
It is not a typical thing but now I need a routine that is simple, fast,
efficient and puts the elements of a sequence into random order. The best I could
come up with is this.
function unsort(sequence x)
integer lx,px,py
object bx
lx=length(x)
bx=x[1]
x[1]=0
py=1
for i=1 to lx by 1 do
px=rand(lx)
x[py]=x[px]
py=px
end for
x[py]=bx
return x
end function
Any more efficient code? Any better idea?
Thanks in advance!
Salix
2. Re: question unsort(x)
Hi Salix.
You can find a better method in my General Functions package, under the
name "Scramble".
The method I used is due to Donald Knuth, as far as I recall.
Yours is faster, but it does not guarantee a truly random order,
since there may be some elements that are never exchanged.
Regards.
3. Re: question unsort(x)
Salix wrote:
>
> It is not a typical thing but now I need a routine that is simple, fast,
> efficient
> and puts the elements of a sequence into random order. The best I could come
> up with is this.
>
> }}}
<eucode>
> function unsort(sequence x)
> integer lx,px,py
> object bx
> lx=length(x)
> bx=x[1]
> x[1]=0
> py=1
> for i=1 to lx by 1 do
> px=rand(lx)
> x[py]=x[px]
> py=px
> end for
> x[py]=bx
> return x
> end function
> </eucode>
{{{
>
> Any more efficient code? Any better idea?
>
> Thanks in advance!
>
> Salix
Hello Salix,
When I have had to do this, I have found it more useful to use a function I
call RandSequence(). It returns a sequence of the same size as the original
sequence and which has randomized indexes. Thus the original sequence is
untouched, but I can use its "randomized shadow" sequence to do what is
needed. Here is a possible sort of use:
sequence shuffled
shuffled=RandSequence(originalSequence)
for i=1 to length(originalSequence) do
puts(1,originalSequence[shuffled[i]]&'\n')
end for
--Quark
4. Re: question unsort(x)
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
