Does anyone know how to pseudo-randomize an array (eg with a seed) so
that you get the same order every time you do it?
thanks
max
···
--
Posted via http://www.ruby-forum.com/.
Max Williams <toastkid.williams@gmail.com> writes:
Does anyone know how to pseudo-randomize an array (eg with a seed) so
that you get the same order every time you do it?
Using a pseudo-random number generator, seeded with the same seed.
Another way would be to just use the seed to index the permutations of
the array, but you would need big seeds for non-small arrays...
···
--
__Pascal Bourguignon__
Hi --
···
On Thu, 3 Jul 2008, Max Williams wrote:
Does anyone know how to pseudo-randomize an array (eg with a seed) so
that you get the same order every time you do it?
Use Kernel#srand.
David
--
Rails training from David A. Black and Ruby Power and Light:
Intro to Ruby on Rails July 21-24 Edison, NJ
Advancing With Rails August 18-21 Edison, NJ
See http://www.rubypal.com for details and updates!
a.sort{ rand }
but I do not know about a seed.
Cheers
Robert
···
--
http://ruby-smalltalk.blogspot.com/
---
AALST (n.) One who changes his name to be further to the front
D.Adams; The Meaning of LIFF
Max Williams wrote:
Does anyone know how to pseudo-randomize an array (eg with a seed) so
that you get the same order every time you do it?
If I've understood the problem correctly, can't you set up a lookup
table for the array indices? You don't have to change the array itself.
The lookup table can be an array, e.g.
t[0] = 1
t[1] = 4
t[2] = 2
t[3] = 3
t[4] = 0
Then if the original array is arr, instead of accessing arr[i] you'd
access arr[t[i]].
···
--
Posted via http://www.ruby-forum.com/\.
ruby19 has a Array#shuffle method:
irb(main):001:0> Kernel.srand(1); [1,2,3,4,5].shuffle
=> [2, 4, 1, 5, 3]
irb(main):002:0> Kernel.srand(1); [1,2,3,4,5].shuffle
=> [2, 4, 1, 5, 3]
···
On Jul 3, 4:56 pm, Max Williams <toastkid.willi...@gmail.com> wrote:
Does anyone know how to pseudo-randomize an array (eg with a seed) so
that you get the same order every time you do it?
Thanks guys
This is what i did in the meantime since asking (I monkey-patched
Array):
class Array
def randomize(seed=nil)
srand(seed) if seed
self.sort{|a,b| rand <=> rand }
end
def randomize!(seed=nil)
srand(seed) if seed
self.sort!{|a,b| rand <=> rand }
end
end
I'm worried though that using sort like this is a bit inefficient. The
array being sorted is around 3000 numbers (and not likely to exceed
5000) so maybe that's not too much of an issue. Is there a more
efficient way you can think of?
···
--
Posted via http://www.ruby-forum.com/.
a.sort{ rand }
Don't do that:
>> a = (1..5).to_a
=> [1, 2, 3, 4, 5]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
Use a.sort_by { rand } instead.
James Edward Gray II
···
On Jul 3, 2008, at 11:04 AM, Robert Dober wrote:
ThoML wrote:
···
On Jul 3, 4:56 pm, Max Williams <toastkid.willi...@gmail.com> wrote:
Does anyone know how to pseudo-randomize an array (eg with a seed) so
that you get the same order every time you do it?ruby19 has a Array#shuffle method:
irb(main):001:0> Kernel.srand(1); [1,2,3,4,5].shuffle
=> [2, 4, 1, 5, 3]
irb(main):002:0> Kernel.srand(1); [1,2,3,4,5].shuffle
=> [2, 4, 1, 5, 3]
I'm only on 1.8.6 (and not likely to change soon since we'd want to do
all our work servers as well), but out of interest, do you know how
shuffle compares to .sort_by{rand} (thanks rob!) in terms of efficiency?
--
Posted via http://www.ruby-forum.com/\.
Hi --
···
On Fri, 4 Jul 2008, Max Williams wrote:
Thanks guys
This is what i did in the meantime since asking (I monkey-patched
Array):class Array
def randomize(seed=nil)
srand(seed) if seed
self.sort{|a,b| rand <=> rand }
enddef randomize!(seed=nil)
srand(seed) if seed
self.sort!{|a,b| rand <=> rand }
endend
I'm worried though that using sort like this is a bit inefficient. The
array being sorted is around 3000 numbers (and not likely to exceed
5000) so maybe that's not too much of an issue. Is there a more
efficient way you can think of?
I absolutely wouldn't worry about it, unless you actually notice any
slowness.
David
--
Rails training from David A. Black and Ruby Power and Light:
Intro to Ruby on Rails July 21-24 Edison, NJ
Advancing With Rails August 18-21 Edison, NJ
See http://www.rubypal.com for details and updates!
Oh, you meant to show this behavior. My bad.
James Edward Gray II
···
On Jul 3, 2008, at 11:08 AM, James Gray wrote:
On Jul 3, 2008, at 11:04 AM, Robert Dober wrote:
a.sort{ rand }
Don't do that:
>> a = (1..5).to_a
=> [1, 2, 3, 4, 5]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
Use sort_by{rand} and you'll call rand once per element (O(n)) rather than twice per comparison (O(n*log(n)))
-Rob
Rob Biedenharn http://agileconsultingllc.com
Rob@AgileConsultingLLC.com
···
On Jul 3, 2008, at 11:57 AM, Max Williams wrote:
Thanks guys
This is what i did in the meantime since asking (I monkey-patched
Array):class Array
def randomize(seed=nil)
srand(seed) if seed
self.sort{|a,b| rand <=> rand }
enddef randomize!(seed=nil)
srand(seed) if seed
self.sort!{|a,b| rand <=> rand }
endend
I'm worried though that using sort like this is a bit inefficient. The
array being sorted is around 3000 numbers (and not likely to exceed
5000) so maybe that's not too much of an issue. Is there a more
efficient way you can think of?
It looks like it should be faster for larger arrays. There are actually two
methods Array#shuffle! and Array#shuffle
Here's a Ruby translation of the C code:
class Array
def shuffle!
i = length - 1
while (i > 0)
j = rand(i)
# Swap self[i] and self[j]
# This might be more elegant using a parallel assignment, but
# parallel assignment generates a temporary array, so this is
# a little closer to the C code
tmp = self[i]
self[i] = self[j]
self[j] = self[i]
i -= 1
end
self
end
def shuffle
self.dup.shuffle!
end
end
So shuffle is O(n) whereas any sort is going to be O(>n)
···
On Thu, Jul 3, 2008 at 12:59 PM, Max Williams <toastkid.williams@gmail.com> wrote:
ThoML wrote:
> On Jul 3, 4:56 pm, Max Williams <toastkid.willi...@gmail.com> wrote:
>> Does anyone know how to pseudo-randomize an array (eg with a seed) so
>> that you get the same order every time you do it?
>
> ruby19 has a Array#shuffle method:
> irb(main):001:0> Kernel.srand(1); [1,2,3,4,5].shuffle
> => [2, 4, 1, 5, 3]
> irb(main):002:0> Kernel.srand(1); [1,2,3,4,5].shuffle
> => [2, 4, 1, 5, 3]I'm only on 1.8.6 (and not likely to change soon since we'd want to do
all our work servers as well), but out of interest, do you know how
shuffle compares to .sort_by{rand} (thanks rob!) in terms of efficiency?
--
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/
James you should know me better 
He does not want sort_by{ rand } he
explicitely asked for deterministic results, thus
sort{ rand }.
But yet James is right of course, even if for the wrong reason here.
First of all you cannot set the seed, second of all it will not be
portable (jruby reverses for example, while ruby1.8 and ruby1.9 do the
same right now), and I guess that this is not guaranteed behavior at
all.
So after all I have to admit it was not my brightest idea to introduce
this "pattern" OTOH I had worse ideas.
Cheers
Robert
···
On Thu, Jul 3, 2008 at 6:08 PM, James Gray <james@grayproductions.net> wrote:
On Jul 3, 2008, at 11:04 AM, Robert Dober wrote:
a.sort{ rand }
Don't do that:
a = (1..5).to_a
=> [1, 2, 3, 4, 5]
a.sort { rand }
=> [5, 3, 1, 4, 2]
a.sort { rand }
=> [5, 3, 1, 4, 2]
a.sort { rand }
=> [5, 3, 1, 4, 2]
Use a.sort_by { rand } instead.
James Edward Gray II
--
http://ruby-smalltalk.blogspot.com/
---
AALST (n.) One who changes his name to be further to the front
D.Adams; The Meaning of LIFF
Hi Max,
How about a very small change:
class Array
def randomize(seed=nil)
srand(seed) if seed
sort_by { rand }
srand # re-seed random number generator
end
def randomize!(seed=nil)
replace(randomize(seed))
end
end
Because the seed used to generate random values (via Kernel#rand) is
global, if you switch it back, you'll (likely) affect random numbers
across your entire Ruby instance. I don't know if this will have any
effect on your current project, but should you ever integrate this
technique on another project, it could cause a problem.
Eric
···
On Jul 3, 11:57 am, Max Williams <toastkid.willi...@gmail.com> wrote:
This is what i did in the meantime since asking (I monkey-patched
Array):class Array
def randomize(seed=nil)
srand(seed) if seed
self.sort{|a,b| rand <=> rand }
enddef randomize!(seed=nil)
srand(seed) if seed
self.sort!{|a,b| rand <=> rand }
endend
====
LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops. Please visit http://LearnRuby.com for all the details.
I would suggest using sort_by { |a| rand }
Otherwise, you could trigger a pathological case if the algorithm depends
on the assumption that every comparison of any two elements will yield the
same results. (sort_by caches the values it generates, so that doesn't
happen.)
···
On 2008-07-03, Max Williams <toastkid.williams@gmail.com> wrote:
class Array
def randomize(seed=nil)
srand(seed) if seed
self.sort{|a,b| rand <=> rand }
end
--
Copyright 2008, all wrongs reversed. Peter Seebach / usenet-nospam@seebs.net
| Seebs.Net <-- lawsuits, religion, and funny pictures
Fair game (Scientology) - Wikipedia <-- get educated!
David A. Black wrote:
I absolutely wouldn't worry about it, unless you actually notice any
slowness.
Cool, if there's a problem i'll say David A. Black told me it would be
ok 
thanks everyone
···
--
Posted via http://www.ruby-forum.com/\.
Hi --
···
On Fri, 4 Jul 2008, James Gray wrote:
On Jul 3, 2008, at 11:08 AM, James Gray wrote:
On Jul 3, 2008, at 11:04 AM, Robert Dober wrote:
a.sort{ rand }
Don't do that:
>> a = (1..5).to_a
=> [1, 2, 3, 4, 5]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]
>> a.sort { rand }
=> [5, 3, 1, 4, 2]Oh, you meant to show this behavior. My bad.
It's not really even pseudo-random, though -- it's just what you get
if you always say that a <=> b is > 0. [1,2,3,4,5].sort { 1 } does the
same thing. So every 5-element array will shuffle the same way, which
I don't think is what the OP wanted.
David
--
Rails training from David A. Black and Ruby Power and Light:
Intro to Ruby on Rails July 21-24 Edison, NJ
Advancing With Rails August 18-21 Edison, NJ
See http://www.rubypal.com for details and updates!
# Swap self[i] and self[j]
# This might be more elegant using a parallel assignment, but
# parallel assignment generates a temporary array, so this is
# a little closer to the C code
tmp = self[i]
self[i] = self[j]
self[j] = self[i]
There's a typo here the line above should be self[j] = tmp
···
On Thu, Jul 3, 2008 at 1:44 PM, Rick DeNatale <rick.denatale@gmail.com> wrote:
i -= 1
end
self
enddef shuffle
self.dup.shuffle!
end
endSo shuffle is O(n) whereas any sort is going to be O(>n)
--
Rick DeNataleMy blog on Ruby
http://talklikeaduck.denhaven2.com/
--
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/
Rick Denatale wrote:
class Array
def shuffle!
i = length - 1
while (i > 0)
j = rand(i)
# Swap self[i] and self[j]
# This might be more elegant using a parallel assignment, but
# parallel assignment generates a temporary array, so this is
# a little closer to the C code
tmp = self[i]
self[i] = self[j]
self[j] = tmp
i -= 1
end
self
end
So shuffle is O(n) whereas any sort is going to be O(>n)
I'm still on 1.8.6, which doesn't have shuffle, but i'll use this
algorithm in my own randomize method, it's nice.
Eric, thanks for the suggestion about unseeding rand before returning,
good idea.
Thanks again, guys, great stuff.
···
--
Posted via http://www.ruby-forum.com/\.