JavaScript: 「フィッシャー–イェーツのシャッフル」を読んで関数にしてみた



[フィッシャー–イェーツのシャッフル(wikipedia)](https://ja.wikipedia.org/wiki/フィッシャー–イェーツのシャッフル#改良されたアルゴリズム)から引用：

> フィッシャー–イェーツのシャッフル (英: Fisher–Yates shuffle) は、有限集合からランダムな順列を生成するアルゴリズムである。言い換えると、有限列をランダムな別の（シャッフルされた）順序の有限列に並べ直す方法である。

なるほど。
「生成する」のか「並べ直す」のか ふわっとしてる...多分両方です。
ちなみにこの記事では、なるべく破壊的変更をしない方向にしていこうかなと思っています。
「生成する」方向で。


>フィッシャー–イェーツのシャッフルは、帽子に入れた数字の書かれたくじ（組合せ数学的に区別可能なもの）をなくなるまで取り出して並べていく手順に似ている。

なるほど。これだけ読んだらこんなのができました。

```js:
const innerShuffle = acc => xs =>{
  if(xs.length === 0) return acc
  const r = randInt(xs.length)
  return innerShuffle( addElem(xs[r])(acc) )( deleteElemAt(r)(xs) )
}

const shuffle = innerShuffle([])

const randInt = n =>
  Math.floor( Math.random() * n )

const addElem = x => xs =>
  [ ...xs, x ]

const deleteElemAt = i => xs =>
  [...xs.slice(0, i), ...xs.slice(i+1)]

// 使用例：
shuffle([0,1,2,3,4,5])  // 例えば [ 4, 0, 5, 1, 2, 3 ]
```
xs という帽子から一個ずつ とりだして accに並べる、というイメージです。そのまんま。
世の中であまり見かけないけど、これでいいんでないの?
# フィッシャーとイェーツによるアルゴリズム
省略。紙とペンと乱数表でやるそうな。
#[改良されたアルゴリズム](https://ja.wikipedia.org/wiki/フィッシャー–イェーツのシャッフル#改良されたアルゴリズム)
普通見かけるのがこちら：

> ダステンフェルドのアルゴリズムとフィッシャー–イェーツのそれには、小さいが決定的な差異が存在する。フィッシャー–イェーツの手法を単純にコンピュータで実装する場合、上記の手順3において、残っている数を数え上げるという不要な時間を要する。対してダステンフェルドの手法では「消す」数字を、残っている数字の中で最後の数字と入れ替え、数列の最後に移動させる。

```js:
const array = [0, 1, 2, 3, 4]
let r
let temp
for(let i = array.length - 1; i >= 0; i--){
  r = Math.floor(Math.random()*( i + 1));
  temp = array[i];
  array[i] = array[r];
  array[r] = temp;
}
console.log(array)
```
こんな感じかな?
これを、元の配列は変更せずシャッフルした新しい配列を返す関数にします。

```js:
//for-loopで:
const randInt = n => 
  Math.floor( Math.random() * n )

const shuffle = xs =>{
  const array = [...xs]
  for(let i = array.length - 1; i>=0; i--){
    const r = randInt( i + 1 );
    [ array[i], array[r] ] = [ array[r], array[i] ]
  }
  return array
}

//--------------------------------
//for-ofで:
const randInt = n => 
  Math.floor( Math.random() * n )

const shuffle = xs =>{
  const array = [...xs]
  for(const i of [...array.keys()].reverse()){
    const r = randInt( i + 1 );
    [ array[i], array[r]] = [array[r], array[i] ]
  }
  return array
}

//--------------------------------
//reduceRight() を使って:
const randInt = n => 
  Math.floor( Math.random() * n )

const init = xs => [...xs]
const update = (acc, _, i) =>{
  const r = randInt( i + 1 );
  [ acc[i], acc[r] ] = [ acc[r], acc[i] ]
  return acc
}

const shuffle = xs =>
  xs.reduceRight( update, init(xs) )
```
値を交換するところは、[配列の分割代入](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment)を使っています。

# [「取り出し」アルゴリズム](https://ja.wikipedia.org/wiki/フィッシャー–イェーツのシャッフル#「取り出し」アルゴリズム)

> 配列の初期化とシャッフルを同時に行う場合であれば、「取り出し」版のシャッフルを使うことで少し効率よく行うことができる。このやり方では、配列の添字 i を増やしながら処理を行う。まず生成配列の i 番目に、配列の初めから i までの中でのランダムな場所 j 番目の値を移動し、その後に元配列の i 番目の値を、生成配列の j 番目に代入する。

ちょっと何いってるかわからない...
けれどコードにしてみたら なるほどなー という感じ。
前から攻めていくのと、swapしないですむところが違いです。

いきなり関数バージョンでいきます。

```js:
//for-loopで：
const randInt = n => 
  Math.floor( Math.random() * n )

const shuffle = xs =>{
  const array = [...xs]
  for(let i = 0; i <= array.length - 1; i++){
    const r = randInt( i + 1 );
    array[i] = array[r];
    array[r] = xs[i] ;
  }
  return array
}

//------------------------
//for-ofで：
const randInt = n => 
  Math.floor( Math.random() * n )

const shuffle = xs =>{
  const array = [...xs]
  for(const i of array.keys()){
      const r = randInt( i + 1 );
      array[i] = array[r];
      array[r] = xs[i] ;
  }
  return array
}

//------------------------
//reduce() を使って：
const randInt = n => 
  Math.floor( Math.random() * n )

const init = xs => [...xs]
const update = (acc, e, i) =>{
  const r = randInt( i + 1 );
  acc[i] = acc[r];
  acc[r] = e;
  return acc
}

const shuffle = xs =>
  xs.reduce( update, init(xs) )
```

以下略。