1. question unsort(x)
- Posted by Salix <salix at ?reemai?.hu> Aug 05, 2007
- 548 views
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)
- Posted by Ricardo Forno <ricardoforno at tutop?a.c?m> Aug 05, 2007
- 522 views
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)
- Posted by DB James <larches at ?om?ast.net> Aug 05, 2007
- 523 views
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)
- Posted by Fernando Bauer <fmbauer at hotmail.co?> Aug 07, 2007
- 540 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