配列をシャッフルするアルゴリズムを思いついたが既存だった話【JavaScript/Rubyサンプルコードあり】

０．前提

　アルゴリズムそのものは筆者自身がゼロから考えました。もし他の方の考えたアルゴリズムと同じだったとしてもごめんなさい。アルゴリズム界隈にそこまで詳しくないのでこれが有名なアルゴリズムだったとしても知らない
　→追記：どうやら、フィッシャー–イェーツのシャッフル - Wikipediaという有名なヤツらしいです。本当に何も知らなかったんです。信じてください。ここから先、サンプルコードを書いてる途中で気づくまでウッキウキで解説してる筆者の展望をご覧ください。書き直すのも億劫なのでそのままにしておきます。

１．アルゴリズム

　さて、このアルゴリズムはもともと前回【JavaScript】重複のない乱数配列を作ってみた【ES6(ES2015)】でアルゴリズムを考えていたときに生まれたものです。もし気になるならそっちも見てみてください。
　前回に続いて『アルゴリズムこうしん～♪』とかやろうと思いましたが今回はやめておきます。
　先にアルゴリズムを説明しておくことにしましょう。サンプルコードは私が書ける言語の範囲（）でこの下に書いておきます。
　ひとまず、要素数5の配列で説明します。ほぼ前回のと同じですが笑。

initAry：

添字	0	1	2	3	4
要素	kurorin	kotone	hime	hina	tyanmari

　この配列をシャッフルするよ！

　０～４（initAryの添字の最大値）の乱数を発生させて、initAryからその乱数の位置にある要素を一つ取り出し新しい配列randAryに入れるよ。

randomNumber:3
取り出す要素はinitAry[3] = hime
initAry：

| 添字 | 0 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 要素 | kurorin | kotone | hina | tyanmari |

randAry:

| 添字 | 0 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 要素 | hime |

　これを、initAryが空になるまで繰り返すよ。
　０～３（initAryの添字の最大値）の乱数を発生させて、initAryからその乱数の位置にある要素を一つ取り出し配列randAryに入れるよ。

randomNumber:2
取り出す要素はinitAry[2] = hina

initAry：

| 添字 | 0 | 1 | 2 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 要素 | kurorin | kotone | tyanmari |

randAry:

| 添字 | 0 | 1 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 要素 | hime | hina |

　・・・（略）・・・

randomNumber:0
取り出す要素はinitAry[0] = kotone
initAry：

| 添字 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 要素 |

randAry:

添字	0	1	2	3	4
要素	hime	hina	kurorin	tyanmari	kotone

　さて、要素数5の配列がシャッフルできたよ！
　これを要素数nの配列でやればシャッフルできるよ！すっごーい！

３．サンプルコード

　そこまで難しくないと思うので、解説は簡略化します。

JavaScript（ES6）

//min以上max未満の乱数を発生させる関数
const getRandomInt =(min, max) => {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min)) + min;
}

//配列をシャッフルする関数
const getRandomAry = (ary) => {
  const initAry = ary.slice();
  let randAry = [];
  while(initAry.length > 0){
    randAry.push(initAry.splice(getRandomInt(0,initAry.length), 1).pop());
  }
  return randAry;
}

　ES6（ES2015）のアロー関数を用いているので、非対応環境ではfunctionとか使って書いてください。
　わざわざconst initAry = ary.slice();と二度手間を踏んでいるのは値渡しをするためです。これをしないと、参照渡しとなり、関数呼び出し時に引数として渡した配列が空になってしまうためです。アロー関数だと引数が配列の場合、参照渡し参照の値渡しになりその配列を破壊的に操作されるようですね・・・。別で記事まとめました→【JavaScript】配列を引数渡しすると破壊的に動作する話【メモ書き】

Ruby

def get_random_array(initAry)
  randAry = Array.new
  while(initAry.length > 0)
    randAry.push(initAry.slice!(rand(initAry.length)))
  end
  return randAry
end

　コード書いてて何故か処理が終わらないな・・・と思ってたらslice!をsliceと書いていて破壊的メソッドになっていないからでした。
　ってか、書いてみたけどArrayクラスにshuffleってメソッドあるじゃん。というわけでそれを使いましょう。

~~　C++　~~

#include<vector>

～サンプルコード作成途中の話～
　・・・ん？　なんかstd::shuffleってのがあるな？

以下の実装では、フィッシャー - イェーツのシャッフルアルゴリズムが使用されている
shuffle - cpprefjp C++日本語リファレンス

　「フィッシャー - イェーツのシャッフル」・・・？
　～Wikipediaを読む筆者～

　・・・。

　・・・・・・。

　一緒じゃねえか！！
　誰がねェ・・・誰がどう見ても、おんなじやおんなじや思てェ！！
　うわああああああああああああああああああああああああああん！！！！
　・・・書きかけのサンプルコード、乗りかかった船だし
　やってやろうじゃねえか！まあゆくどりさんは天才ですから？！？！
　（何でも言うことを聞いてくれるアカネチャン風）
　ということで動的配列vectorを使って書こうとしました。

　・・・・・・。

　が。乱数生成の段階で詰まりました。DxLibくらいでしか触れたことのない私ではまだ無理でした。ヘッダとか色々読みましたが、最近のC++ではC言語のrand()やsrand()を使うのは非推奨なようで、よく理解してない私が「これがサンプルコードです」と提示すると界隈の方々に叩かれそうなので止めました。また理解できるようになってから覚えていたら帰ってきてここに書くことにします。

４．参考文献

JavaScriptで配列のコピー（値渡し） - Qiita
るりまサーチ（サンプルコード作成時リファレンスの検索に使用）
shuffle - cpprefjp C++日本語リファレンス

５．さいごに

　結局、思いついたのは既存アルゴリズムでした。まあ、このアルゴリズムを自分で思いついたのでよく理解できていますし、損はしないと思っています。また何か思いついたりしたら書きます。
　ありがとうございました。