# Pseudo-randomize an array in a consistent order

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

AALST (n.) One who changes his name to be further to the front

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 DeNatale

My blog on Ruby

Rick DeNatale

My blog on Ruby

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

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 }
end

end

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

AALST (n.) One who changes his name to be further to the front

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.