JavaScript で シャッフルする

# はじめに

`JavaScript`で`Array`の中身をシャッフルしたいことがあり、
そういえばどういう仕組みなんだろうと考えたことがきっかけで調べてみることにしました。

# フィッシャー–イェーツの手法

[ウィキペディア](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC%E2%80%93%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB)を参考に考えてみます。

## 前提

ここに`1`から`5`までの数字が格納された配列があります。
これをフィッシャー–イェーツの手法でシャッフルしてみます。

```js
array = [1, 2, 3, 4, 5]
```

## 1. `1` から `N` までの数字を書く。

前提で準備した配列の状態から `N` は `5` です。

```js
[1, 2, 3, 4, 5]
```

## 2. まだ消されてない数字の数を数え、`1` からその数以下までのランダムな数字 `k` を選ぶ。

`まだ消されていない数字の数` は `5`(`array.length`)です。
配列なので`0`から`4`までのランダムな数字 `k` を求めます。

```js
n = array.length
k = Math.floor(Math.random() * n); // 3
```

ランダムな数字 `3` が出力されました。

## 3. 残っている数字から `k` 番目の数字を消し、別の場所にその数字を書き出す。

配列 `array` の `3` 番目の数字を別の配列( `newArray` )に移します。
配列 `array` の `3` 番目を削除します。

```js
newArray = []

newArray.push(array[k]);  // array の3番目を newArray に追加
array.splice(k, 1);       // array の3番目を削除

console.log(newArray);    // [4]
console.log(array);       // [1, 2, 3, 5]
```

## 4. すべての数字が消されるまで手順 `2`, `3` を繰り返す。

`array`の`length`が`0`になるまで繰り返すそうです。
1回目から`array`の`length`が`0`になるまで繰り返してみます。

| `n` | `array`     | `newArray` | `k` | `3`の手順実行後の`array` | `3`の手順実行後の`newArray` |
| :-- | :---------- | :--------- | :-- | :-------------------- | :------------------------ |
| 5   | [1,2,3,4,5] | []         | 3   | [1,2,3,5]             | [4]                       |
| 4   | [1,2,3,5]   | [4]        | 0   | [2,3,5]               | [4,1]                     |
| 3   | [2,3,5]     | [4,1]      | 2   | [2,3]                 | [4,1,5]                   |
| 2   | [2,3]       | [4,1,5]    | 1   | [2]                   | [4,1,5,3]                 |
| 1   | [2]         | [4,1,5,3]  | 0   | []                    | [4,1,5,3,2]               |

※`n`は`array`の残り個数、`k`は`0`から`n`までのランダムな数字です。

## 5. 手順 `3` で書かれた数列が元の数値からのランダム順列となる。

手順 `3` で書かれた数列は `newArray` です。
最終的な`newArray`の値は `[4, 1, 5, 3, 2]` となりました。

## `JavaScript`でやってみる

```js
array = [1, 2, 3, 4, 5];
newArray = [];

while (array.length > 0) {
  n = array.length;
  k = Math.floor(Math.random() * n);

  newArray.push(array[k]);
  array.splice(k, 1);
}

console.log("ランダムな数列", newArray);
```

```sh:出力結果1回目
ランダムな数列 [ 2, 4, 1, 5, 3 ]
```

```sh:出力結果2回目
ランダムな数列 [ 3, 1, 5, 4, 2 ]
```

シャッフルされてそうですね。

# ダステンフェルドの手法

> 上記の手順3において、残っている数を数え上げるという不要な時間を要する。

残っている数を数え上げてるの手順2じゃね？。。。

確かに毎回残っている数を数え上げる処理はもったいない気がしますね。
もし、配列の要素数が大きい場合、時間がかかりそう。

そこで改良されたアルゴリズムが `ダステンフェルドの手法` です。

この方法は添字を利用し、`配列の個数 - 1`回、カウントダウンのループ処理を行います。
ループ毎に`0`から`添字 - 1`までのランダムな数字`k`を求め、
配列の`添字 - 1`番目と`k`番目を交換する方法です。

最後の `1` 回、ループをスキップする理由は、手順の方に書きます。

フィッシャー–イェーツの手順にダステンフェルドの手法を組み込んでみます。

## 1. `1` から `N` までの数字を書く。

準備した配列の状態から `N` は `5` です。

```js
[1, 2, 3, 4, 5]
```

## 2. `0` から添字までのランダムな数字 `k` を選ぶ。

ランダムな数字は `0` から `i - 1`　から求めます。
添字 `i` は、配列の要素数からスタートするので、
初回は `0` から `4` までのランダムな数字を求めます。

この方法で、添字をカウントダウンし、 `N - 1` 回繰り返されます。

ループの最後は `i - 1` が `0`の為、 `0`から`0`までのランダムな数字は`0`です。
配列の`i - 1`番目と`k`番目を交換しますが、 `0` 番目と `0` 番目の交換は意味が無いのでスキップします。

添字 `i` に配列の要素数を定義し、カウントダウンしますが初回のイメージは以下です。

```js
i = array.length
k = Math.floor(Math.random() * i); // 3
```

こちらもランダムな数字 `3` が出力されたものとして考えます。

## 3. `k` 番目の数字を `i - 1` 番目の数字と入れ替える。

この方法では、別の領域(`newArray`)を使いません。

```js
[array[k], array[i - 1]] = [array[i - 1], array[k]]; // array の3番目と4番目を入れ替え

console.log(array);       // [1, 2, 3, 5, 4]
```

## 4. 添字が `0` になるまで手順 `2`, `3` を繰り返す。

```js
for (i = array.length; 1 < i; i--) {
  // 手順 `2`, `3` の処理
}
```

| `i` | `array`     | `k` | `3`の手順実行後の`array` |
| :-- | :---------- | :-- | :--------------------- |
| 5   | [1,2,3,4,5] | 3   | [1,2,3,5,4]            |
| 4   | [1,2,3,5,4] | 0   | [5,2,3,1,4]            |
| 3   | [5,2,3,1,4] | 2   | [5,2,3,1,4]            |
| 2   | [5,2,3,1,4] | 0   | [2,5,3,1,4]            |

※`i`は添字、`k`は`0`から`i - 1`までのランダムな数字です。

## 5. 手順 `3` で書かれた数列が元の数値からのランダム順列となる。

手順 `3` で `array` 内の入れ替えを行っているだけなので `array` が答えです。
最終的な`array`の値は `[2, 5, 3, 1, 4]` となりました。

## `JavaScript`でやってみる

```js:dustenfeld.js
array = [1, 2, 3, 4, 5];

for (i = array.length; 1 < i; i--) {
  k = Math.floor(Math.random() * i);
  [array[k], array[i - 1]] = [array[i - 1], array[k]];
}

console.log("ランダムな数列", newArray);
```

```sh:出力結果1回目
ランダムな数列 [ 4, 2, 1, 5, 3 ]
```

```sh:出力結果2回目
ランダムな数列 [ 3, 2, 4, 5, 1 ]
```

こちらもちゃんとシャッフルされてそうですね。

# 計測してみる

## 配列の要素数 10件

|   fisherYates |    dustenfeld |
| ------------: | ------------: |
|     0.00011 s | **0.00006 s** |
|     0.00008 s | **0.00006 s** |
|     0.00012 s | **0.00006 s** |
| **0.00009 s** |     0.00018 s |
|     0.00008 s | **0.00006 s** |


あまり差はでないですね。

## 配列の要素数 10万件

| fisherYates |    dustenfeld |
| ----------: | ------------: |
|   1.93609 s | **0.00702 s** |
|   2.12999 s | **0.00746 s** |
|   1.92727 s | **0.00681 s** |
|   1.93922 s | **0.00691 s** |
|   1.98414 s | **0.00679 s** |

書き方かもしれませんが、ダステンフェルドの手法が断トツ速いです。

# 終わりに
`Ruby`には`shuffle`メソッドがあるので、楽ですね。

ソースは[こちら](https://github.com/pure-adachi/js-shuffle)に置いてます。

# 参考文献

- [フィッシャー–イェーツのシャッフル - wiki](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC%E2%80%93%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB)
- [ALG009_ダステンフェルドのシャッフル](http://ozateck.sakura.ne.jp/wordpress/2018/09/05/alg009_%E3%83%80%E3%82%B9%E3%83%86%E3%83%B3%E3%83%95%E3%82%A7%E3%83%AB%E3%83%89%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB/)