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
Max W. [email protected] 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…
Hi –
On Thu, 3 Jul 2008, Max W. 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
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?
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
Hi –
On Fri, 4 Jul 2008, Max W. wrote:
end
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
On Jul 3, 2008, at 11:04 AM, Robert D. 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 G. II
On Jul 3, 2008, at 11:08 AM, James G. wrote:
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.
James Edward G. II
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
Hi –
On Fri, 4 Jul 2008, James G. wrote:
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
On Jul 3, 2008, at 11:57 AM, Max W. wrote:
end
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?
Use sort_by{rand} and you’ll call rand once per element (O(n)) rather
than twice per comparison (O(n*log(n)))
-Rob
Max W. 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]].
On Jul 3, 4:56 pm, Max W. [email protected] 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]
ThoML wrote:
On Jul 3, 4:56 pm, Max W. [email protected] 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?
On Thu, Jul 3, 2008 at 1:44 PM, Rick DeNatale [email protected]
wrote:
# 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
So 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/
On Thu, Jul 3, 2008 at 12:59 PM, Max W.
[email protected]
wrote:
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?
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)
–
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/
On Jul 3, 11:57 am, Max W. [email protected] wrote:
def randomize!(seed=nil)
srand(seed) if seed
self.sort!{|a,b| rand <=> rand }
endend
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
====
LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops. Please visit http://LearnRuby.com for all the details.
On 2008-07-03, Max W. [email protected] wrote:
class Array
def randomize(seed=nil)
srand(seed) if seed
self.sort{|a,b| rand <=> rand }
end
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 Thu, Jul 3, 2008 at 6:08 PM, James G. [email protected]
wrote:
a.sort { rand }
=> [5, 3, 1, 4, 2]
a.sort { rand }
=> [5, 3, 1, 4, 2]Use a.sort_by { rand } instead.
James Edward G. II
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
–
http://ruby-smalltalk.blogspot.com/
AALST (n.) One who changes his name to be further to the front
D.Adams; The Meaning of LIFF
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.