pseudo-randomize an array in a consistent order

M

Max Williams

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
 
P

Pascal J. Bourguignon

Max Williams said:
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...
 
D

David A. Black

Hi --

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
 
M

Max Williams

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?
 
D

David A. Black

Hi --

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?

I absolutely wouldn't worry about it, unless you actually notice any
slowness.


David
 
R

Rob Biedenharn

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?


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
(e-mail address removed)
 
M

Max Williams

David said:
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
 
D

David A. Black

Hi --

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
 
D

Dave Bass

Max said:
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 you'd
access arr[t].
 
T

ThoML

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]
 
M

Max Williams

ThoML said:
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?
 
R

Rick DeNatale

[Note: parts of this message were removed to make it a legal post.]

ThoML said:
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?


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 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
self = self[j]
self[j] = self
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)
 
R

Rick DeNatale

[Note: parts of this message were removed to make it a legal post.]

# Swap self 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
self = self[j]
self[j] = self


There's a typo here the line above should be self[j] = tmp
 
R

Robert Dober

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


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
 
E

Eric I.

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


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.
 
S

Seebs

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.)
 
M

Max Williams

Rick said:
class Array
def shuffle!
i = length - 1
while (i > 0)
j = rand(i)
# Swap self 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
self = 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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top