サイズNの配列からM個の要素をランダムに取り出す

問題

サイズNの配列からM個の要素を取り出し新たな配列を返すメソッドを実装する。各要素が選ばれる確率は全て等確率になるようにする。

解き方

はじめに元々の配列の先頭からM個取り出して配列を作る。後は、インデックスがm以上の要素と以下の要素を交換するチャンスを等しく与えてあげることで、等確率をつくることができる。

ソースコード