From: Himadri Choudhury <hchoudh@...>
Date: 2006-04-24T04:39:50+09:00
Subject: Re: [QUIZ] Text Munger (#76)

------=_Part_6426_19493065.1145821187582
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

> On 4/23/06, Albert Vernon Smith <smithav@cshl.edu> wrote:
> Also, for a swap method to give random results doesn't one need to
> swap from a random position in the array which has not been passed
> through yet?  (see http://en.wikipedia.org/wiki
>
> /Shuffle noting Fisher-
> Yates shuffling.)
>

Yes. You are right. My memory didn't serve me well in this case.
Instead of j =3D rand(i+1), it should have been: j =3D i + rand(x.length-i)

Thanks for the reference.

Himadri

On 4/23/06, Albert Vernon Smith <smithav@cshl.edu> wrote:
>
> Is the performance better if you skip swaps when i =3D=3D j ?
>
> Also, for a swap method to give random results doesn't one need to
> swap from a random position in the array which has not been passed
> through yet?  (see http://en.wikipedia.org/wiki/Shuffle noting Fisher-
> Yates shuffling.)
>
> -a
>
> On 23.4.2006, at 09:45, Himadri Choudhury wrote:
>
> > print ARGF.read.gsub!(/\B[a-z]+\B/) {|x|
> >     x.length.times {|i|
> >         j =3D rand(i+1)
> >         x[j], x[i] =3D x[i] , x[j]
> >     }
> >     x
> > }
> >
> > Basically, this is an implementation of scrambling that uses swaps. I
> > remember this method for scrambling from way back, but I can't seem
> > to find
> > a good reference for it at the moment.
> > I also figured that this method would be faster since it is linear,
> > while
> > the sorts are n log(n) (n =3D length of the word)
> >
> > To by surprise, I found this method to actually be slower for any
> > normal
> > text. One possible explanation is that when words are relatively
> > short you
> > don't gain much from the n vs. nlogn difference, and you lose
> > because while
> > this method always has n swaps, sorting may have less.
>
>
>

------=_Part_6426_19493065.1145821187582--