[ruby-list:39597] Re: ruby-ver? 配列のランダム化

原です。

ちょっと気になったので、、

In [ruby-list:39588]

> class Array
>   def randomize!
>    　result = collect{ slice!(rand(length)) }
>      replace result
>   end
> 
>   def randomize
>      arr=self.dup
>      arr.randomize!
>      arr
>   end
> end

これって動かなくなったんですね。
こんなふうにすればいいですね。

  class Array
    def randomize
      arr = dup
      collect{ arr.slice!(rand(arr.length)) }
    end
  
    def randomize!
      replace(randomize)
    end
  end


それから、

In [ruby-list:39591]

> >class Array
> >  def randomize
> >    sort_by{ rand(100) }
> >  end
> >
> >  def randomize!
> >    replace randomize
> >  end
> >end

> これだと、要素数が 100 を上回るときにあまりランダムにな
> らないかもしれませんね。
> rand(100) => rand(100 * length) とかすればいいかもしれません。

これはやはり sort を使うこと自体が、コスト高であるのが気に
なります。

さらに、randomize の精度が sort のアルゴリズム依存であって、
例えば stable な sort であるとすると、順序が変わらない確率
が若干高いです。いくら確率を対象としているといって、アルゴ
リズムが確率的なのは気持ち悪いです。（気持ち悪くない人もい
るかも。）

In [ruby-list:39594]
>新谷です。
>直感的に、配列に乱数を割り当てて、sortしていることに相当す
>るのかと思いました。
>sort_byをよく理解していないのですが、ただのrandでは、いけ
>ないのでしょうか。

これは、

    sort_by{ rand() }

とするという事ですよね。いいと思います。多分 rand(整数) の
方が乱数生成のコストが低いんでしょうが、「rand界」も随分進
化しているので、あまり気にしなくてもいいんでしょう。

先と同じ理由で、まだ少し気持ち悪さが残るのですが。


In [ruby-list:39593]

> class Array
>   def randomize!
>     length.times do |i1|
>       i2 = rand(length)
>       t = self[i1]
>       self[i1] = self[i2]
>       self[i2] = t
>     end
>   end
> 
>   def randomize
>     result = self.dup
>     result.randomize!
>     result
>   end
> end

こちらは、アルゴリズムとしてまずいのでは？手で計算する
と [1, 2, 3] をシャッフルして 2 が先頭に来る確率は 10/27
みたい。もちろん 1/3 であるべきですよね。
#そもそも手計算で正答する確率がかなり低いのですが(^^;

  def randomize!
    (length-1).downto(0) do |i1|
      i2 = rand(i1+1)
      t = self[i1]
      self[i1] = self[i2]
      self[i2] = t
    end
  end

だったらいいかな。

スピードは最初の slice のが速いみたいですね。

一番美しいのは r = rand(nの階乗) を一発だけ計算して、後で
ゴソゴソするアルゴリズムだと思うんですが、r を配列に「デ
コード」するコストが大きくてあまり速くならなそう。