Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
16
Help us understand the problem. What is going on with this article?
@shoheiyokoyama

Fisher-Yates shufflアルゴリズムを用いて自作で配列をシャッフルさせる

More than 5 years have passed since last update.

RubyやPython、Underscore.jsなどにはshuffle関数があり、簡単に配列の順番をランダムに入れ替えることはできますが、自作で配列やリストをランダムに入れ替える場合に、Fisher-Yates shuffleというアルゴリズムがあるので共有したいと思います

Fisher-Yates shuffle

Fisher-Yates shuffleは配列からランダムに要素を抽出し、入れ替えるアルゴリズムです。

  var length = array.length;
  for(var i = length - 1; i > 0; i--) {
      var j = Math.floor(Math.random() * (i + 1));
      var tmp = array[i];
      array[i] = array[j];
      array[j] = tmp;
  }

(Fisher-Yates shuffleアルゴリスムは英語版Wikipedia'Fisher-Yates shuffle'参照)

このアルゴリスムの特徴をまとめると以下のようになります

  • 配列の全ての要素が最低1回ずつ入れ替えの対象となる
  • 入れ替えられた要素が2回入れ替わることはない
  • 配列の長さ分の計算量なので計算コストがかからなく高速
  • 理論上偏りがない結果が得られる

最後に

シンプルかつ最適化されたアルゴリスムなので、要素をランダムに入れ替えるのアルゴリスムとしては最も有名だと思います。shuffle関数がない言語などで使ってみるといいですね

他の言語に用いられているshuffle関数については、こちらが参考になります
swiftでシャッフル関数
リストをシャッフルする
CoffeeScriptで配列のシャッフル

この記事も参考になります
Array#sort実装のshuffleは偏る

16
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
shoheiyokoyama
【横山 祥平 / @shoheiyokoyama 】 iOS Engineer at SmartNews, Inc. EX-CyberAgent, Inc. AbemaTV, WinTicket, CyberLDH. Medium: https://medium.com/@shoheiyokoyama
cyberagent
サイバーエージェントは「21世紀を代表する会社を創る」をビジョンに掲げ、インターネットテレビ局「AbemaTV」の運営や国内トップシェアを誇るインターネット広告事業を展開しています。インターネット産業の変化に合わせ新規事業を生み出しながら事業拡大を続けています。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
16
Help us understand the problem. What is going on with this article?