JavaScriptで非復元抽出を実装する 🎁

元来、抽選方法には「復元抽出」と「非復元抽出」がありまして、

復元抽出
抽出された要素を除外せずに再び母集団に戻して無作為抽出を行う抽選方法

非復元抽出
無作為抽出を何度か繰り返して行う場合、既に抽出された要素を母集団から除外して無作為抽出を行う

という違いがあります。（Wikipediaより）

現実のガチャガチャは「非復元抽出」であることが多く、ソーシャルゲームのガチャは「復元抽出」であることが多いですね。
で、実際プログラムを書くときの抽選で「非復元抽出」を使いたいケースというのは多々ありまして、TypeScriptで実装してみました。

TypeScript

class Fukubiki {
  private maxLength: number;
  private length: number;
  private pod: number[];
  private autoReset: boolean;
  private callback: () => void;

  constructor(length: number = 0, param: {
    autoReset?: boolean;
    callback?: () => void;
  } = {}) {
    this.maxLength = this.length = length;
    this.pod = [];
    this.autoReset = param.autoReset || false;
    this.callback = param.callback || function() {};

    for (let i = 0; i < this.length; ++i) {
      this.pod.push(i);
    }
  }

  public reset(): void {
    this.pod.splice(0, this.pod.length);

    for (let i = 0; i < this.maxLength; ++i) {
      this.pod.push(i);
    }

    this.length = this.maxLength;
  }

  public select(): number | null {
    const num = this.pod.splice(Math.random() * this.pod.length | 0, 1)[0];

    this.length = this.pod.length;

    if (!this.pod.length) {
      if (this.autoReset) {
        this.reset();
      }

      this.callback.call(this);
    }

    return typeof num === 'number' ? num : null;
  }
}

export default Fukubiki;

つかいかた

import Fukubiki from 'fukubiki';

const fukubiki = new Fukubiki(10); // 0 ~ 9を収納する

fukubiki.select(); // 1つ取り出す

基本的には、こんな感じで使います。
空になった際の処理の実装を迷ったのですが、デフォルトの挙動は空になった際は特に何もせず、その後はnullを返すようにしました。

import Fukubiki from 'fukubiki';

const fukubiki = new Fukubiki(1); // 0が収納される

fukubiki.select(); // 1つ取り出す => 0
fukubiki.select(); // 1つ取り出す => null
fukubiki.select(); // 1つ取り出す => null

ただ、空になった際に通知が欲しい場合もあると思うので、optionでコールバックを渡せます。

import Fukubiki from 'fukubiki';

const fukubiki = new Fukubiki(1, {
  callback: () => {
    alert('empty!');
  }
}); // 0が収納される

fukubiki.select(); // 1つ取り出す => 0（アラートが表示される）
fukubiki.select(); // 1つ取り出す => null
fukubiki.select(); // 1つ取り出す => null

あと、空になった際に自動的に初期状態に戻すoptionもあります。

import Fukubiki from 'fukubiki';

const fukubiki = new Fukubiki(1, {
  autoReset: true
}); // 0が収納される

fukubiki.select(); // 1つ取り出す => 0
fukubiki.select(); // 1つ取り出す => 0
fukubiki.select(); // 1つ取り出す => 0

意外と便利なので、よく使ってます。
非復元抽出は英語だと「sampling without replacement」になるのですが、npmで検索しても出てこなかったので、登録しておきました。

www.npmjs.com

絶対に誰もつくってない訳ないと思うんですが、どんな名前で登録されているのかが気になるところです。