From: Peter <Peter.Vanbroekhoven@...>
Date: 2003-09-18T00:52:57+09:00
Subject: Re: scrambler one-liner

> Actually, no.  The point is to have a random distribution.  It is certainly
> conceivable that sort{rand} might not produce a sufficiently random
> distribution.  For instance, if sort were using something like a bubble
> sort, then a value might not "bubble" too far from its original position
> because the random comparisons only move it a few positions before the
> random comparisons are satisfied.
> 
> Note that I'm not saying sort *does* work this way.  One would have to
> analyse the situation before one could say.  I'm merely saying it is
> possible.

I don't know if bubble sort using a random number for comparisons is
always a good idea. Bubble sort runs over the array and compares two
subsequent values and swaps them if they are out of order. It keeps doing
that until there are no more swaps during a run. Suppose the test says two
values are out of order about 1 times out of 4. If your array is 100
elements large, the chance of a run doing swaps is 1-(1-0.25)**100, which
evaluates to 0.999999999999679 The mean number of runs needed by
bubblesort is then 3117982410207. Of course for words of 15 characters
this is only 75 runs, and most words are shorter. If you need to get a
random permutation of an array of 100 numbers, use another technique. The
following piece of code is linear in the number of elements to sort, and
has the added bonus that each reordering is equally likely. It's not a
one-liner, but that's the job for you guys :-)

  def reorder(str)
    result = []
    while str.length > 0
      result << str.delete_at(rand(str.length))
    end
    result
  end

  def scramble(str)
    str.gsub!(/\B\w+\B/){reorder($&.split(//)).join}
  end

Peter