1. random numbers
I am trying to generate 52 random numbers 1-52 without duplicating any numbers.
it seems every time I try I get duplications. Does anyone have a
solution for this.
Thanks
Allen
2. Re: random numbers
Allen Ashby wrote:
>
>
> I am trying to generate 52 random numbers 1-52 without duplicating any
> numbers.
> it seems every time I try I get duplications. Does anyone have a
> solution for this.
>
include misc.e
function Shuffle()
sequence ShuffledDeck
integer temp
ShuffledDeck = {}
while length(ShuffledDeck) < 52 do
temp = rand(52)
if not find(temp, ShuffledDeck) then
ShuffledDeck &= temp
end if
end while
return ShuffledDeck
end function
-- Unit tests
sequence test
if find("--unittest", command_line()) then
puts(2, "Doing unit testing\n")
test = Shuffle()
if length(test) != 52 then
printf(2, "Length is %d and not 52\n", length(test))
end if
for i = 1 to length(test) do
if find(test[i], test[i+1..$]) then
printf(2, "Dup %d at %d\n", {test[i], i})
end if
end for
end if
--
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell
3. Re: random numbers
Allen Ashby wrote:
>
> I am trying to generate 52 random numbers 1-52 without duplicating any
> numbers.
> it seems every time I try I get duplications. Does anyone have a
> solution for this.
Start with a sequence {1..52} and pull them from that.
s = {1,2,3,4,5,6,7,8,9,...52}
n = {}
for t=1 to 52 do
r = rand(length(s)) -- grab a random position
n &= s[r] -- add it to our new sequence
s = s[1..r-1] & s[r+1..$] -- remove from available numbers
end for
4. Re: random numbers
Derek Parnell wrote:
> function Shuffle()
> sequence ShuffledDeck
> integer temp
> ShuffledDeck = {}
> while length(ShuffledDeck) < 52 do
> temp = rand(52)
> if not find(temp, ShuffledDeck) then
> ShuffledDeck &= temp
> end if
> end while
> return ShuffledDeck
> end function
Wouldn't that possibly take too long generating the last number? You have a
51 out of 52 chance of picking a number the already exists. Nevermind...
here's a test:
include misc.e
include get.e
function Shuffle()
sequence ShuffledDeck
integer temp
ShuffledDeck = {}
while length(ShuffledDeck) < 52 do
temp = rand(52)
if not find(temp, ShuffledDeck) then
ShuffledDeck &= temp
end if
end while
return ShuffledDeck
end function
function shuff()
sequence s, n
integer r
s = {}
for t=1 to 52 do
s &= t
end for
n = {}
for t=1 to 52 do
r = rand(length(s)) -- grab a random position
n &= s[r] -- add it to our new sequence
s = s[1..r-1] & s[r+1..$] -- remove from available numbers
end for
return n
end function
atom c, t
sequence test
c=0
t = time() + 3
while t > time() do
test = Shuffle()
c += 1
end while
?c
c = 0
t = time() + 3
while t > time() do
test = shuff()
c += 1
end while
?c
if wait_key() then end if
5. Re: random numbers
Derek Parnell wrote:
> function Shuffle()
> sequence ShuffledDeck
> integer temp
> ShuffledDeck = {}
> while length(ShuffledDeck) < 52 do
> temp = rand(52)
> if not find(temp, ShuffledDeck) then
> ShuffledDeck &= temp
> end if
> end while
> return ShuffledDeck
> end function
Wouldn't that possibly take too long generating the last number? You have a
51 out of 52 chance of picking a number the already exists. Nevermind...
here's a test:
include misc.e
include get.e
constant fittytwo =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
function Shuffle()
sequence ShuffledDeck
integer temp
ShuffledDeck = {}
while length(ShuffledDeck) < 52 do
temp = rand(52)
if not find(temp, ShuffledDeck) then
ShuffledDeck &= temp
end if
end while
return ShuffledDeck
end function
function shuff()
sequence s, n
integer r
s = {}
for t=1 to 52 do
s &= t
end for
n = {}
for t=1 to 52 do
r = rand(length(s)) -- grab a random position
n &= s[r] -- add it to our new sequence
s = s[1..r-1] & s[r+1..$] -- remove from available numbers
end for
return n
end function
function shuff2()
sequence s, n
integer r
s = repeat(0,52)
for t=1 to 52 do
s[t] = t
end for
n = {}
for t=1 to 52 do
r = rand(length(s)) -- grab a random position
n &= s[r] -- add it to our new sequence
s = s[1..r-1] & s[r+1..$] -- remove from available numbers
end for
return n
end function
function shuff3()
sequence s, n
integer r
s = fittytwo
n = {}
for t=1 to 52 do
r = rand(length(s)) -- grab a random position
n &= s[r] -- add it to our new sequence
s = s[1..r-1] & s[r+1..$] -- remove from available numbers
end for
return n
end function
atom c, t
sequence test
c=0
puts(1,"Starting test...\n\n")
t = time() + 3
while t > time() do
test = Shuffle()
c += 1
end while
?c
c = 0
t = time() + 3
while t > time() do
test = shuff()
c += 1
end while
?c
c = 0
t = time() + 3
while t > time() do
test = shuff2()
c += 1
end while
?c
c = 0
t = time() + 3
while t > time() do
test = shuff3()
c += 1
end while
?c
if wait_key() then end if
6. Re: random numbers
Sorry for the double-post... The first one didn't seem to go through and I
figured out faster ways to go...
OpenEuphoria.org is acting up a lot lately. :(
7. Re: random numbers
c.k.lester wrote:
>
> Allen Ashby wrote:
> >
> > I am trying to generate 52 random numbers 1-52 without duplicating any
> > numbers.
> > it seems every time I try I get duplications. Does anyone have a
> > solution for this.
>
> Start with a sequence {1..52} and pull them from that.
>
> s = {1,2,3,4,5,6,7,8,9,...52}
> n = {}
> for t=1 to 52 do
> r = rand(length(s)) -- grab a random position
> n &= s[r] -- add it to our new sequence
> s = s[1..r-1] & s[r+1..$] -- remove from available numbers
> end for
This would have been my solution as well. Nice!
I would only change it slightly:
s = {1,2,3,4,5,6,7,8,9,...52}
n = repeat(0, 52)
for t=1 to 52 do
r = rand(length(s)) -- grab a random position
n[t] = s[r] -- add it to our new sequence
s = s[1..r-1] & s[r+1..$] -- remove from available numbers
end for
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
8. Re: random numbers
Jason Gade wrote:
> I would only change it slightly:
> }}}
<eucode>
> s = {1,2,3,4,5,6,7,8,9,...52}
> n = repeat(0, 52)
> for t=1 to 52 do
> r = rand(length(s)) -- grab a random position
> n[t] = s[r] -- add it to our new sequence
> s = s[1..r-1] & s[r+1..$] -- remove from available numbers
> end for
> </eucode>
{{{
Good eye! :)
9. Re: random numbers
sequence s
function shuffle(sequence s) -- random shuffle of sequence
object temp
integer r
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
s =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
s = shuffle(s)
10. Re: random numbers
c.k.lester wrote:
> Wouldn't that possibly take too long generating the last number? You have a
> 51 out of 52 chance of picking a number the already exists. Nevermind...
> here's a test:
Well no one mentioned that speed was an issue. I just tried to demonstrate a
simple algorithm, I wasn't after speed. However, if you want speed, try this
adjustment to your fastest routine ...
function shuff4()
sequence s, n
integer r
s = fittytwo
n = repeat(0,52)
for t=52 to 2 by -1 do
r = rand(t) -- grab a random position
n[t] = s[r] -- add it to our new sequence
s[r..51] = s[r+1..52]-- remove from available numbers
end for
n[1] = s[1]
return n
end function
On my machine I get ...
shuff: 20-22% improvement
shuff2: 24-27% improvement
shuff3: 25-30% improvement
shuff4: 85-95% improvement
The shuff4() routine avoids unnecessary calculations, and memory allocations and
deallocations.
--
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell
11. Re: random numbers
jiri babor wrote:
Hey jiri! I knew I should have left it to the master. Your routine is about 385%
faster than my first try. It is the same as mine but very sensibly reuses the
very sequence that is being shuffled for the result storage. That really
eliminates all the excess memory allocation and moving stuff about.
... if only there was a built-in swap operation for even faster run times.
function shuffle(sequence s) -- random shuffle of sequence
integer r
for i = length(s) to 2 by -1 do
r = rand(i)
swap s[r] with s[i] !!!
end for
return s
end function
--
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell
12. Re: random numbers
Yes, Derek, a built-in swap function would be more useful than endless
discussions how to simulate a simple goto with a dozen fancy constructs...
jiri
13. Re: random numbers
Derek Parnell wrote:
>
> jiri babor wrote:
>
> Hey jiri! I knew I should have left it to the master. Your routine is about
> 385% faster than my first try. It is the same as mine but very sensibly reuses
> the very sequence that is being shuffled for the result storage. That really
> eliminates all the excess memory allocation and moving stuff about.
>
> ... if only there was a built-in swap operation for even faster run times.
>
> function shuffle(sequence s) -- random shuffle of sequence
> integer r
> for i = length(s) to 2 by -1 do
> r = rand(i)
> swap s[r] with s[i] !!!
> end for
> return s
> end function
>
> --
> Derek Parnell
> Melbourne, Australia
> Skype name: derek.j.parnell
Shuffling algorithm: nothing to add, solved optimally while I was sleeping.
Swap operation: I am not sure swap(sequence s,integer index1,integer index2)
would be much faster than current
temp=s[index1]
implicit_temp=s[index2]
s[index1]=implicit_temp
s[index2]=temp
because of the overhead of routine calls. At the machine level, you can of
course shave implicit_temp using the three XCHG trick:
<asm>
xchg eax,[ebx+esi]
wchg eax,[ebx+edi]
xchg eax,[ebx+esi]
</asm>
with obvious register usage. I don't know if supported C compilers can apply it,
and it wouldn't work on non Intel CPUs (ARM processor standard architecture
doesn't have an XCHG instruction).
What would speed up some tasks is a builtin move_right(sequence s,integer
start_slice,integer end_slice,integer how_much). Currently you have to do this by
creating temporary slices:
temp=s[end_slice+1..end_slice+how_much]
s[start_slice+how_much..end_slice+how_much]=s[start_slice..end_slice]
s[start_slice..start_slice+how_much-1]=temp
In the backend you just need EMalloc()ing some memory for the end portion, three
memcpy() and an EFree(). Wraparounds should probably trigger a runtime error, but
could be handled with a couple more memcpy() calls. Of course negative values for
how_much would be allowed.
CChris
14. Re: random numbers
CChris wrote:
>
> Derek Parnell wrote:
>> ... if only there was a built-in swap operation for even faster run times.
>> swap s[r] with s[i] !!!
>
> Swap operation: I am not sure swap(sequence s,integer index1,integer index2)
> would be much faster than current
> }}}
<eucode>
> temp=s[index1]
> implicit_temp=s[index2]
> s[index1]=implicit_temp
> s[index2]=temp
> </eucode>
{{{
> because of the overhead of routine calls.
I said swap OPERATION and not swap FUNCTION. The idea being that there would be
an in-built operation, like the arithmetic operations, that performs optimal swap
functionality so we wouldn't have a function call overhead.
--
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell
15. Re: random numbers
Derek Parnell wrote:
>
>
> I said swap OPERATION and not swap FUNCTION. The idea being that there would
> be an in-built operation, like the arithmetic operations, that performs
> optimal
> swap functionality so we wouldn't have a function call overhead.
>
> --
Derek:
A suggestion for a swap operator to swap two variable:
first_variable >< second_variable
Bernie
My files in archive:
WMOTOR, XMOTOR, W32ENGIN, MIXEDLIB, EU_ENGIN, WIN32ERU, WIN32API
Can be downloaded here:
http://www.rapideuphoria.com/cgi-bin/asearch.exu?dos=on&win=on&lnx=on&gen=on&keywords=bernie+ryan
16. Re: random numbers
Derek Parnell wrote:
> function shuff4()
> ...
> end function
>
> On my machine I get ...
>
> shuff: 20-22% improvement
> shuff2: 24-27% improvement
> shuff3: 25-30% improvement
> shuff4: 85-95% improvement
>
> The shuff4() routine avoids unnecessary calculations, and memory allocations
> and deallocations.
That's awesome, Derek!
17. Re: random numbers
Derek Parnell wrote:
> Hey jiri! I knew I should have left it to the master. Your routine is about
> 385% faster than my first try.
Yeah, Jiri's is fast! So, how do you measure randomness?
I know there are tests for it. I'm wondering if jiri's algorithm allows for
every possible permutation. I sped up your original first try, Derek. Look
at shuff3(). But I don't know if that ruins the algorithm or messes with
the randomness.
Here's an updated look:
include misc.e
include get.e
constant fittytwo =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
sequence tests
tests = {{},{}}
procedure add_test(sequence name, atom id)
tests[1] = append(tests[1],name)
tests[2] &= id
end procedure
function shuff1()
sequence s, n
integer r
s = fittytwo
n = repeat(0,52)
for t=1 to 52 do
r = rand(length(s)) -- grab a random position
n[t] = s[r] -- add it to our new sequence
s = s[1..r-1] & s[r+1..$] -- remove from available numbers
end for
return n
end function
function shuff3()
sequence s, n
integer r
s = fittytwo
n = repeat(0,52)
for t=52 to 2 by -1 do
r = rand(t) -- grab a random position
n[t] = s[r] -- add it to our new sequence
s[r..51] = s[r+1..52]-- remove from available numbers
end for
n[1] = s[1]
return n
end function
function shuff4()
sequence s, n
integer r
s = fittytwo
n = repeat(0,52)
for t=52 to 2 by -1 do
r = rand(t) -- grab a random position
n[t] = s[r] -- add it to our new sequence
s[r..t-1] = s[r+1..t]-- remove from available numbers -- Derek, this is
what I changed
end for
n[1] = s[1]
return n
end function
function shuff5()
object temp
integer r
sequence s
s = fittytwo
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
procedure run_tests()
atom c, t
sequence test
integer secs
for x=1 to length( tests[1]) do
c=0
secs = 1
puts(1,"Starting test " & tests[1][x] & "\n")
t = time() + secs
while t > time() do
test = call_func(tests[2][x],{})
c += 1
end while
?test
printf(1,"\t%d\n\n",{c})
end for
end procedure
add_test("Baseline",routine_id("shuff1"))
add_test("Derek's First",routine_id("shuff3"))
add_test("Derek's First Modified",routine_id("shuff4"))
add_test("Jiri's Speed Demon",routine_id("shuff5"))
run_tests()
puts(1,"\nDone! Press any key to quit.")
if wait_key() then end if
18. Re: random numbers
c.k.lester wrote:
>
> I sped up your original first try, Derek. Look at shuff3().
Obviously I meant shuff4(). :)
19. Re: random numbers
c.k.lester wrote:
>
> Derek Parnell wrote:
> > Hey jiri! I knew I should have left it to the master. Your routine is about
> > 385% faster than my first try.
>
> Yeah, Jiri's is fast! So, how do you measure randomness?
> I know there are tests for it. I'm wondering if jiri's algorithm allows for
> every possible permutation. I sped up your original first try, Derek. Look
> at shuff3(). But I don't know if that ruins the algorithm or messes with
> the randomness.
>
> Here's an updated look:
>
> }}}
<eucode>include misc.e
> include get.e
>
> constant fittytwo =
> {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
>
> sequence tests
> tests = {{},{}}
>
> procedure add_test(sequence name, atom id)
> tests[1] = append(tests[1],name)
> tests[2] &= id
> end procedure
>
> function shuff1()
> sequence s, n
> integer r
> s = fittytwo
> n = repeat(0,52)
> for t=1 to 52 do
> r = rand(length(s)) -- grab a random position
> n[t] = s[r] -- add it to our new sequence
> s = s[1..r-1] & s[r+1..$] -- remove from available numbers
> end for
> return n
> end function
>
> function shuff3()
> sequence s, n
> integer r
> s = fittytwo
> n = repeat(0,52)
> for t=52 to 2 by -1 do
> r = rand(t) -- grab a random position
> n[t] = s[r] -- add it to our new sequence
> s[r..51] = s[r+1..52]-- remove from available numbers
> end for
> n[1] = s[1]
> return n
> end function
>
> function shuff4()
> sequence s, n
> integer r
> s = fittytwo
> n = repeat(0,52)
> for t=52 to 2 by -1 do
> r = rand(t) -- grab a random position
> n[t] = s[r] -- add it to our new sequence
> s[r..t-1] = s[r+1..t]-- remove from available numbers -- Derek, this is
> what I changed
> end for
> n[1] = s[1]
> return n
> end function
>
> function shuff5()
> object temp
> integer r
> sequence s
> s = fittytwo
> 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
>
> procedure run_tests()
> atom c, t
> sequence test
> integer secs
>
> for x=1 to length( tests[1]) do
> c=0
> secs = 1
>
> puts(1,"Starting test " & tests[1][x] & "\n")
>
> t = time() + secs
> while t > time() do
> test = call_func(tests[2][x],{})
> c += 1
> end while
> ?test
> printf(1,"\t%d\n\n",{c})
> end for
>
> end procedure
>
> add_test("Baseline",routine_id("shuff1"))
> add_test("Derek's First",routine_id("shuff3"))
> add_test("Derek's First Modified",routine_id("shuff4"))
> add_test("Jiri's Speed Demon",routine_id("shuff5"))
>
> run_tests()
>
> puts(1,"\nDone! Press any key to quit.")
> if wait_key() then end if</eucode>
{{{
An almost identical routine is included in my General Functions package.
Here it is:
--/topic STATISTICS / PROBABILITIES ROUTINES
--/func Scramble(sequence s)
--/desc Scrambles, that is, disorders a sequence
--/ret The argument in random order
--Returns sequence 's' scrambled, that is, the resulting sequence contains
-- the elements of 's' in random order.
--Example: Scramble("Mandrake") might give "kadnMare"
global function Scramble(sequence s)
integer len, k
object temp
len = length(s)
for i = 1 to len do
k = rand(len)
temp = s[k]
s[k] = s[i]
s[i] = temp
end for
return s
end function
I later learnt that Donald Knuth was probably the first one to design this
algorithm, and that he showed it really randomly ordered (or disordered 
) a
sequence.
Regards.
20. Re: random numbers
Derek Parnell wrote:
>
> CChris wrote:
> >
> > Derek Parnell wrote:
> >> ... if only there was a built-in swap operation for even faster run times.
> >> swap s[r] with s[i] !!!
>
> >
> > Swap operation: I am not sure swap(sequence s,integer index1,integer index2)
> > would be much faster than current
> > }}}
<eucode>
> > temp=s[index1]
> > implicit_temp=s[index2]
> > s[index1]=implicit_temp
> > s[index2]=temp
> > </eucode>
{{{
> > because of the overhead of routine calls.
>
> I said swap OPERATION and not swap FUNCTION. The idea being that there would
> be an in-built operation, like the arithmetic operations, that performs
> optimal
> swap functionality so we wouldn't have a function call overhead.
>
> --
> Derek Parnell
> Melbourne, Australia
> Skype name: derek.j.parnell
Ok, this will avoid the overhead of the call. Yet I wonder how much speed you
can gain this way wrt current sequene of assignments. At least you'll gain
clearer code - not a small benefit.
CChris
21. Re: random numbers
jiri babor wrote:
>
> sequence s
>
> function shuffle(sequence s) -- random shuffle of sequence
> object temp
> integer r
> 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
>
> s =
> {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52}
> s = shuffle(s)
Good to see you, jiri!
Derek Parnell wrote:
>
> c.k.lester wrote:
> > Wouldn't that possibly take too long generating the last number? You have a
> > 51 out of 52 chance of picking a number the already exists. Nevermind...
> > here's a test:
>
> Well no one mentioned that speed was an issue. I just tried to demonstrate a
> simple algorithm, I wasn't after speed. However, if you want speed, try this
> adjustment to your fastest routine ...
>
> function shuff4()
> sequence s, n
> integer r
> s = fittytwo
> n = repeat(0,52)
> for t=52 to 2 by -1 do
> r = rand(t) -- grab a random position
> n[t] = s[r] -- add it to our new sequence
> s[r..51] = s[r+1..52]-- remove from available numbers
> end for
> n[1] = s[1]
> return n
> end function
I never thought that speed was an issue myself -- I just thought that it was a
simpler or more elegant way of doing things.
Yes, jiri's is best though.
jiri babor wrote:
>
> Yes, Derek, a built-in swap function would be more useful than endless
> discussions
> how to simulate a simple goto with a dozen fancy constructs...
>
> jiri
Well, while I'm one of the "anti-gotos" and prefer a few clear constructs
instead, I think that there are quite a few interesting sequence operations that
I would like to see built-in to the interpreter.
Then again, we always discuss them and never come to any kind of consensus.
Does any other compiled or interpreted language have a built-in swap? I can't
recall coming across one, even though it is a pretty common operation.
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
22. Re: random numbers
- Posted by Juergen Luethje <j.lue at g?x.d?>
Nov 22, 2007
-
Last edited Nov 23, 2007
Hello Ricardo,
you wrote:
<snip>
> An almost identical routine is included in my General Functions package.
> Here it is:
>
> --/topic STATISTICS / PROBABILITIES ROUTINES
> --/func Scramble(sequence s)
> --/desc Scrambles, that is, disorders a sequence
> --/ret The argument in random order
> --Returns sequence 's' scrambled, that is, the resulting sequence contains
> -- the elements of 's' in random order.
> --Example: Scramble("Mandrake") might give "kadnMare"
> global function Scramble(sequence s)
> integer len, k
> object temp
> len = length(s)
> for i = 1 to len do
> k = rand(len)
> temp = s[k]
> s[k] = s[i]
> s[i] = temp
> end for
> return s
> end function
>
> I later learnt that Donald Knuth was probably the first one to design
> this algorithm, and that he showed it really randomly ordered
> (or disordered )
As far as I can see, your Scramble() function above is _not_ a correct
implementation of the so-called Knuth shuffle (see e.g.
<http://en.wikipedia.org/wiki/Knuth_shuffle>).
On that page, in the chapter "Implementation errors" it reads:
| Similarly, always selecting k from the entire range of valid array
| indexes [...] also produces a result which is biased, albeit less
| obviously so. This can be seen from the fact that doing so yields N^N
| distinct possible sequences of swaps, whereas there are only N!
| possible permutations of an N-element array. Since N^N can never be
| evenly divisible by N! (as the latter is divisible by N−1, which shares
| no prime factors with N), some permutations must be produced by more of
| the NN sequences of swaps than others.
Fernando Bauer already had written something similar some months ago:
<http://www.openeuphoria.org/cgi-bin/esearch.exu?fromMonth=6&fromYear=1&toMonth=B&toYear=C&postedBy=&keywords=pigeonhole>
According to my understanding, the code posted here by Jiri Babor is a
correct implementation of the Knuth shuffle.
Regards,
Juergen
23. Re: random numbers
- Posted by Juergen Luethje <j.lue at g??.de>
Nov 22, 2007
-
Last edited Nov 23, 2007
Hi Jason,
you wrote:
<snip>
> Does any other compiled or interpreted language have a built-in swap?
Oh yes, oh yes!
> I can't
> recall coming across one, even though it is a pretty common operation.
It is implemented in many BASIC flavours:
SWAP a, b
Also interesting in this regard is Lua. Lua allows multiple assignment
in one command, e.g.:
a, b = 1, 3
which is the same as:
a = 1
b = 3
This feature can be used for swapping:
a, b = b, a
No joke, that actually works fine in Lua. Cool, no?
Regards,
Juergen
24. Re: random numbers
- Posted by Jason Gade <jaygade at y?ho?.com>
Nov 22, 2007
-
Last edited Nov 23, 2007
Juergen Luethje wrote:
>
> Hi Jason,
>
> you wrote:
>
> <snip>
>
> > Does any other compiled or interpreted language have a built-in swap?
>
> Oh yes, oh yes!
>
> > I can't
> > recall coming across one, even though it is a pretty common operation.
>
> It is implemented in many BASIC flavours:
> SWAP a, b
Heh. The last time that I wrote in BASIC was on an 8-bit machine and it required
line numbers.
> Also interesting in this regard is Lua. Lua allows multiple assignment
> in one command, e.g.:
> a, b = 1, 3
> which is the same as:
> a = 1
> b = 3
>
> This feature can be used for swapping:
> a, b = b, a
>
> No joke, that actually works fine in Lua. Cool, no?
>
> Regards,
> Juergen
I've always thought that Lua was a pretty cool implementation of Euphoria...
;)
--
A complex system that works is invariably found to have evolved from a simple
system that works.
--John Gall's 15th law of Systemantics.
"Premature optimization is the root of all evil in programming."
--C.A.R. Hoare
j.
25. Re: random numbers
- Posted by Ricardo Forno <ricardoforno at t?t?pia.com>
Nov 22, 2007
-
Last edited Nov 23, 2007
Yes, Juergen. My method is biased. I thought it was identical to Knuth's, but it
wasn't, as you pointed out.
I will change it next time I post a modified General Functions.
Best regards.
