配列をシャッフルし、それぞれのインデックスの要素が、元の配列の該当インデックス要素と異なるようにするアルゴリズムです。
A, B, Cを A, C, Bではなく、 C, A, Bのようにシャッフルします。
あ、前回の記事が400番目の記事でした。また記念イベントを忘れてました...
アルゴリズム解説
まずシャッフル元の配列は重複する要素が存在せず、長さが2以上と仮定します。重複している場合は知りません。長さ1の時はシャッフルしても重複するので知りません。
元の配列と同じ位置に同じ要素が来なければいいので、以下のようにすると上手くいきます。
- 1つ目の要素は位置nの要素を入れる(nは1つ目とは違い、ランダムであるとする)。
- 位置nに、まだ選んでない要素からランダムに選んで入れる
- iを更新しながら2を繰り返す
- 最後に空いている位置に0(=1つ目の要素)を入れて終了
すでに選んであれば、そこに重複した要素が入ることはありません。
サンプル動作はこんな感じです
0 1 2 3 4をシャッフルする x x x x x ↓ インデックス0に3を入れる 3 x x x x ↓ インデックス3に2を入れる 3 x x 2 x ↓ インデックス2に1を入れる 3 x 1 2 x ↓ インデックス1に4を入れる 3 4 1 2 x ↓ 最後に空いている位置(=インデックス4) に0(インデックス0だった要素)を入れる 3 4 1 2 0
必ず重複しないことが分かりますね。
コード
function shuffle(N) { let n = 0; const arr = Array(N); const rest = [...Array(N - 1)].map((_, i) => i + 1); // 0は抜いておく // 0番目に値を入れる let _n = 0 | Math.random() * rest.length; arr[0] = rest[_n]; n = rest[_n]; // 今回の値が次のnの値 rest.splice(_n, 1); while (rest.length > 0) { // 以下同様に繰り返す _n = 0 | Math.random() * rest.length; arr[n] = rest[_n]; n = rest[_n]; rest.splice(_n, 1); } arr[n] = 0; // 最後の位置に0を入れて完了 return arr; } console.log(shuffle(4));
これはあくまで入れ替え先インデックスの取得のみ(アルゴリズムの性質上こうせざるを得ない、また、こうしたほうが応用性が高い)なので、実際に入れ替える操作は次のようになります。
const array = ['A', 'B', 'C', 'D', 'E']; const index = shuffle(array.length); const shuffledArray = array.map((_, i) => array[index[i]]); console.log(shuffledArray);
終わりに
実は今回の案件は「他人紹介の組み合わせを決定するプログラム」でした。他人紹介というのは、同じ部活、同じ学年の自分以外の人について紹介する行事のことです。部員全員が1人ずつ書きます。もちろん自分の紹介はできません(つまり重複が許されない)。
...まあたぶん適当に決めますのでこのプログラム使いませんww
