Asp Forum - sorting by rand?

seebs

4/30/2007 2:01:00 AM

Browsing something at a bookstore recently, I saw an example of
an array shuffle allegedly implemented with
x.sort { rand }
or something to that effect.

This seems sort of unlikely, to me, to be a correct shuffling
algorithm. I'm not even sure it's safe at all. I know that
doing the same thing to C qsort implementations occasionally
causes one to blow up spectacularly, because its assumption
that the comparison between any two items is constant gets
broken.

So, two vaguely related questions:
1. Is there a reasonably sane way to do this, should I ever find
myself wanting one?
2. Am I right in guessing that handing garbage to Array#sort
is probably crazy?

-s

3 Answers

Gary Wright

4/30/2007 2:18:00 AM

On Apr 29, 2007, at 10:01 PM, Peter Seebach wrote:
> So, two vaguely related questions:
> 1. Is there a reasonably sane way to do this, should I ever find
> myself wanting one?

Short answer: array.sort_by { rand }

Longer answer: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/...
talk/168963

Gary Wright

Rick DeNatale

4/30/2007 2:37:00 AM

On 4/29/07, Peter Seebach <seebs@seebs.net> wrote:
> Browsing something at a bookstore recently, I saw an example of
> an array shuffle allegedly implemented with
> x.sort { rand }
> or something to that effect.

> This seems sort of unlikely, to me, to be a correct shuffling
> algorithm. I'm not even sure it's safe at all. I know that
> doing the same thing to C qsort implementations occasionally
> causes one to blow up spectacularly, because its assumption
> that the comparison between any two items is constant gets
> broken.
>
> So, two vaguely related questions:
> 1. Is there a reasonably sane way to do this, should I ever find
> myself wanting one?
> 2. Am I right in guessing that handing garbage to Array#sort
> is probably crazy?

I believe that the "something to that effect was probably:

x.sort_by {rand}

sort_by takes a block which normally takes one argument. sort_by
calls this block once for each element of the enumeration and
associates that value with the element, it then sorts those values and
returns an array of the asssociated elements in the order of the
values. So for example:

(1..50).sort_by{|e| -e}
==>[50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36,
35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19,
18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

The block without the argument just assignes a random value to each element.

Perfectly safe as far as I can see.

x.sort {rand}

doesn't really work, whether or not it's safe. Rand without an
argument returns a float >= 0.0 and < 1.0, the block for sort is
expected to return -1, 0, or 1. Depending on the implementaiton of the
particular sort method, you might get different results. For arrays,
it looks like you'll get the same results with repeated calls:

irb(main):020:0> (1..10).to_a.sort {rand}
=> [10, 6, 1, 7, 3, 8, 5, 9, 4, 2]
irb(main):021:0> (1..10).to_a.sort {rand}
=> [10, 6, 1, 7, 3, 8, 5, 9, 4, 2]

Whereas sort_by seems to do what's expected.

irb(main):022:0> (1..10).to_a.sort_by {rand}
=> [5, 9, 2, 1, 7, 6, 4, 10, 8, 3]
irb(main):023:0> (1..10).to_a.sort_by {rand}
=> [4, 8, 5, 6, 2, 3, 10, 7, 1, 9]

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denh...

M. Edward (Ed) Borasky

4/30/2007 6:11:00 AM

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Peter Seebach wrote:
> Browsing something at a bookstore recently, I saw an example of
> an array shuffle allegedly implemented with
> x.sort { rand }
> or something to that effect.
>
> This seems sort of unlikely, to me, to be a correct shuffling
> algorithm. I'm not even sure it's safe at all. I know that
> doing the same thing to C qsort implementations occasionally
> causes one to blow up spectacularly, because its assumption
> that the comparison between any two items is constant gets
> broken.
>
> So, two vaguely related questions:
> 1. Is there a reasonably sane way to do this, should I ever find
> myself wanting one?
> 2. Am I right in guessing that handing garbage to Array#sort
> is probably crazy?
>
> -s
>
>

Welll ... I do this in Excel all the time -- add a column of random
numbers to the right of the (CSV) file I want to shuffle, sort it about
five times, hitting F9 before each sort to change the random numbers,
and then deleting the random column and saving the file. Translate that
to Ruby and I think you've got it.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.3 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail....

iD8DBQFGNYhUaZUb+jwczfoRAgn3AKDJnG8yQYVTWkoPTw9YNT42/6M/OACg1NFg
76A4qzYkZjIIKBA/YAPblDM=
=KVsa
-----END PGP SIGNATURE-----

comp.lang.ruby

sorting by rand?

seebs

Gary Wright

Rick DeNatale

M. Edward (Ed) Borasky

x Login to ForumsZone