Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > need some Ruby magic

Reply
Thread Tools

need some Ruby magic

 
 
Hammed Malik
Guest
Posts: n/a
 
      12-01-2005
------=_Part_9539_13698596.1133466156105
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I'd like to sort collections randomly. This is what I tried first:

my_array.sort { |a,b| rand(2) }
>


but the results weren't very random. I then tried the following:

class Array
> def random_copy
> b =3D Array.new
> while b.length < self.length
> random_value =3D self[rand self.length]
> b.push random_value unless b.include? random_value
> end
> b
> end
> end




This works but I'm sure there's some Ruby magic for doing this better.

thanks

------=_Part_9539_13698596.1133466156105--


 
Reply With Quote
 
 
 
 
David A. Black
Guest
Posts: n/a
 
      12-01-2005
Hi --

On Fri, 2 Dec 2005, Hammed Malik wrote:

> I'd like to sort collections randomly. This is what I tried first:
>
> my_array.sort { |a,b| rand(2) }
>>

>
> but the results weren't very random. I then tried the following:
>
> class Array
>> def random_copy
>> b = Array.new
>> while b.length < self.length
>> random_value = self[rand self.length]
>> b.push random_value unless b.include? random_value
>> end
>> b
>> end
>> end

>
>
>
> This works but I'm sure there's some Ruby magic for doing this better.


I think the most common idiom is:

array.sort_by { rand }


David

--
David A. Black
http://www.velocityreviews.com/forums/(E-Mail Removed)

"Ruby for Rails", forthcoming from Manning Publications, April 2006!


 
Reply With Quote
 
 
 
 
Jim Weirich
Guest
Posts: n/a
 
      12-01-2005
hammed wrote:
> I'd like to sort collections randomly. This is what I tried first:
>
> my_array.sort { |a,b| rand(2) }


my_array.sort_by { rand }

--
Posted via http://www.ruby-forum.com/.


 
Reply With Quote
 
Hammed Malik
Guest
Posts: n/a
 
      12-01-2005
------=_Part_9843_32078302.1133467615836
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

excellent! thanks.

On 01/12/05, Jim Weirich <(E-Mail Removed)> wrote=
:
>
> hammed wrote:
> > I'd like to sort collections randomly. This is what I tried first:
> >
> > my_array.sort { |a,b| rand(2) }

>
> my_array.sort_by { rand }
>
> --
> Posted via http://www.ruby-forum.com/.
>
>


------=_Part_9843_32078302.1133467615836--


 
Reply With Quote
 
Vincent Foley
Guest
Posts: n/a
 
      12-01-2005
Maybe there should be Array#randomize...

 
Reply With Quote
 
Jeff Wood
Guest
Posts: n/a
 
      12-01-2005
------=_Part_13036_22600137.1133473011020
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Take a look @ the Facets project. There are extension methods for array to
have a number of randomized behaviors.

j.

On 12/1/05, Vincent Foley <(E-Mail Removed)> wrote:
>
> Maybe there should be Array#randomize...
>
>
>



--
"Remember. Understand. Believe. Yield! -> http://ruby-lang.org"

Jeff Wood

------=_Part_13036_22600137.1133473011020--


 
Reply With Quote
 
Reinder Verlinde
Guest
Posts: n/a
 
      12-03-2005
In article <(E-Mail Removed)>,
Jim Weirich <(E-Mail Removed)> wrote:

> hammed wrote:
> > I'd like to sort collections randomly. This is what I tried first:
> >
> > my_array.sort { |a,b| rand(2) }

>
> my_array.sort_by { rand }


A quick test seems to indicate that this works with the ruby 1.8.2
implementation on my Mac. However, there is no guarantee that this call
will select each of the n! permutations with equal probability.

Whether it does will depend on the exact algorithm used by 'sort'. For
instance, if sort uses the (inefficient for large arrays) bubble sort,
the last key will end up staying there in half the cases.

Reinder
 
Reply With Quote
 
Stephen Waits
Guest
Posts: n/a
 
      12-03-2005

On Dec 3, 2005, at 9:32 AM, Reinder Verlinde wrote:

> However, there is no guarantee that this call
> will select each of the n! permutations with equal probability.


How about just doing this?

class Array
def shuffle
newarr = self
self.length.times do |x|
y = rand(self.length)
newarr[x], newarr[y] = newarr[y], newarr[x]
end
newarr
end
end

shuffled_array = my_array.shuffle

--Steve



 
Reply With Quote
 
Sam Gentle
Guest
Posts: n/a
 
      12-03-2005
On 12/4/05, Reinder Verlinde <(E-Mail Removed)> wrote:
> In article <(E-Mail Removed)>,
> Jim Weirich <(E-Mail Removed)> wrote:
>
> > hammed wrote:
> > > I'd like to sort collections randomly. This is what I tried first:
> > >
> > > my_array.sort { |a,b| rand(2) }

> >
> > my_array.sort_by { rand }

>
> A quick test seems to indicate that this works with the ruby 1.8.2
> implementation on my Mac. However, there is no guarantee that this call
> will select each of the n! permutations with equal probability.
>
> Whether it does will depend on the exact algorithm used by 'sort'. For
> instance, if sort uses the (inefficient for large arrays) bubble sort,
> the last key will end up staying there in half the cases.


Actually, sort_by caches every value passed and uses those for
comparison (aka a Schwartzian Transform), so it would essentially
return the same results as sorting a list of random numbers,
regardless of algorithm.

Sam


 
Reply With Quote
 
Jim Weirich
Guest
Posts: n/a
 
      12-03-2005
reinder wrote:
>> my_array.sort_by { rand }

>
> A quick test seems to indicate that this works with the ruby 1.8.2
> implementation on my Mac. However, there is no guarantee that this call
> will select each of the n! permutations with equal probability.


Actually, it will. sort_by uses a Schwartzian transform to do the
sorting. That means that rand is only called once for each element of
the array. As long as rand gives a decent distribution of random
numbers, the permutation will be random too.

Here's a little experiment:

-------------------------------------------------
N = (ARGV.shift || 1000).to_i
A = %w(a b c)
Perms = %w(abc acb bac bca cab cba)
Score = Hash.new { |h, k| h[k] = 0 }
N.times do
sorted = A.dup.sort_by { rand }
Score[sorted.join("")] += 1
end

Score.keys.sort.each do |key|
puts "#{key}: #{Score[key]}"
end
-------------------------------------------------

Gives:

$ ruby sortdist.rb 100000
abc: 16693
acb: 16688
bac: 16752
bca: 16590
cab: 16475
cba: 16802

Thats a pretty good distribution for the number of iterations.

-- Jim Weirich


--
Posted via http://www.ruby-forum.com/.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
magic / counter-magic? (detect loading file?) Giles Bowkett Ruby 9 12-17-2007 05:42 AM
Help repost to Ruby Dev -- 2 improvements to Ruby Magic Sunny Hirai Ruby 1 06-06-2007 07:53 AM
Can Ruby do this magic... elegantly J2M Ruby 12 11-12-2006 07:48 PM
Ruby black magic? Meta Programming Tom Willis Ruby 4 03-13-2005 09:15 PM



Advertisments