概要
先日、あるプロジェクトで配列の要素をランダムにシャッフルする必要がありました。TypeScript (5.5.4) には組み込みの shuffle 関数がないため、自分で実装する必要がありました。この記事では、その際に調べたフィッシャーイェーツのシャッフルアルゴリズムについて解説します。
Rubyの配列シャッフル実装
RubyにはArryクラスにsuffle, suffle! という関数があります。
これらの関数は、以下のC言語で書かれているrb_ary_suffle_bang 関数を呼び出しています。
この関数のアルゴリズムはフィッシャーイェーツのシャッフルと言われるものです。特徴は以下の通りです：
- ランダム性: 配列の各要素が等しい確率で任意の位置に移動する。
- インプレース: 配列の要素をその場でシャッフルし、追加のメモリをほとんど使用しない。
- 時間計算量: O(n)の時間でシャッフルを完了する。
- 安定性: 元の順序を保持しないため、安定なソートではない。
- シンプルな実装: アルゴリズムはシンプルで理解しやすい。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| static VALUE
rb_ary_shuffle_bang(rb_execution_context_t *ec, VALUE ary, VALUE randgen)
{
long i, len;
rb_ary_modify(ary);
i = len = RARRAY_LEN(ary);
RARRAY_PTR_USE(ary, ptr, {
while (i) {
long j = RAND_UPTO(i);
VALUE tmp;
if (len != RARRAY_LEN(ary) || ptr != RARRAY_CONST_PTR(ary)) {
rb_raise(rb_eRuntimeError, "modified during shuffle");
}
tmp = ptr[--i];
ptr[i] = ptr[j];
ptr[j] = tmp;
}
}); /* WB: no new reference */
return ary;
}
|
TypeScriptで配列シャッフル実装
この関数は、配列の要素をランダムにシャッフルし、元の配列を変更します。フィッシャーイェーツのアルゴリズムを使用しているため、効率的かつ簡単に実装できます。
1
2
3
4
5
6
7
| const shuffleArray = (array: string[]) => {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
|
おみくじの実装例
上記の関数を使っておみくじを実装してみました。
フィッシャーイェーツ関数でおみくじ | Playground Link
