重複のない乱数を生成するには

英語学習用に音声アシスタント用アプリケーション（下記）を作ったわけですが、どうやらユーザーのご期待に沿えていないようです。ユーザーが先生役を演じることでたくさん発声してみるというコンセプトで作成し、またその説明を聞いてからご利用頂いているはずなのですが、どうもちゃんとご理解を頂けていないことが多そうな感じです。

cheerio-the-bear.hatenablog.com

これでは駄目だということで、ユーザーが生徒役に回る順当な設定で再度アプリケーションを作ろうと思います。練習に用いる例文をアプリケーション側で用意するのが大変だなと思って避けたのですが、やむを得ません。本作はまず Alexa 用に作成して、その後 Google Assistant 用に展開することにしましょう。

例文を重複なく 3 つ選択する

練習に用いる例文は、（簡単なものばかりにしようと思いますが）そこそこの数量が必要になります。いわゆる雑学スキルのサンプルコードのようにコード内で配列として持たせる方法で良いのか、それともデータベース的な外部データにしておくべきなのか。まずは前者でコーディングを進めながら、ひと通り期待通りに動作するようになってから考えましょう。なんてことをやっているうちに、表題の問題が出てきました。

www.atmarkit.co.jp

一度のセッションの中では 3 つの例文を使う仕様にしようと思いますので、例文の配列からそれらを重複なくピックアップしなくてはなりません。上の記事にもある「ダステンフェルドのアルゴリズム」を使うべきかなと思ったのですが、わずか 3 つの選択のために所定範囲内の数値で埋めた配列を用意するのって何だか嫌じゃないですか。そんなことないですか。記事内のコードから引用させて頂くと、この「配列を初期化する」部分です。

  // 指定された範囲の整数を格納できる配列を用意する
  int[] work = new int[rangeEnd - rangeBegin + 1];

  // 配列を初期化する
  for (int n = rangeBegin, i = 0; n <= rangeEnd; n++, i++)
    work[i] = n;

「配列の初期化」だけやめてみる

先ほど「ダステンフェルドのアルゴリズム」の実装例から引用したコードの、for 文のところだけやめて Java Script で書き直してみました。いやいや、その前の「指定された範囲の整数を格納できる配列を用意する」のところも何だか気持ち悪いし、という話の流れになるものと思いながら書いていたのですが、思ったより嫌いじゃないです。

const QUESTIONS = [
    'Question 0',
    'Question 1',
    'Question 2',
    'Question 3',
    'Question 4',
    'Question 5',
    'Question 6',
    'Question 7',
    'Question 8',
    'Question 9'
] // This may contain more than 1000 questions

const NUMBER_OF_QUESTIONS = 3

var questions = Array(QUESTIONS.length)
var list = Array(NUMBER_OF_QUESTIONS)

for (var index1 = 0; index1 < list.length; index1++) {
    let index2 = Math.floor(Math.random() * (questions.length - index1))
            + index1
    let element1 = questions[index1]
    let element2 = questions[index2]
    list[index1] = (element2 != null) ? element2 : index2
    questions[index2] = (element1 != null) ? element1 : index1
}

console.log(list)

NUMBER_OF_QUESTIONS 値を 10 にして走らせてみても、ちゃんと重複なく乱数列を作ってくれていました。

[ 8, 6, 0, 4, 9, 7, 2, 1, 5, 3 ]

この動作確認に利用させて頂いた PlayCode はこちら。

playcode.io

「指定された範囲の整数を格納できる配列を用意する」もやめる

「指定された範囲の整数を格納できる配列を用意する」のも、問題数が多い場合には（10000 とか）あまり気持ち良くはないです。そんな配列を使わずにこの目的を達成しようとすると、どんな方法が使えるんでしょうか。ひとつ書いてみましたが、どうもあまりうまくない。

const QUESTIONS = [
    'Question 0',
    'Question 1',
    'Question 2',
    'Question 3',
    'Question 4',
    'Question 5',
    'Question 6',
    'Question 7',
    'Question 8',
    'Question 9'
] // This may contain more than 1000 questions

const NUMBER_OF_QUESTIONS = 3

var options = QUESTIONS.length
var list = []
var sorted = []

do {
    var selected = Math.floor(Math.random() * options)
    for (var index = 0; index < sorted.length; index++) {
        if (selected < sorted[index]) {
            break
        }
        selected++
    }
    list.push(selected)
    sorted.push(selected)
    sorted.sort((a, b) => a - b)
} while(--options && list.length < NUMBER_OF_QUESTIONS)

console.log(list)

ちゃんと動いていますし、要素数の大きな配列の生成もその初期化も行わなずにやれていますが、安易に push() や sort() を利用してしまいました。用途によっては、パフォーマンス面では目を瞑る必要がありそうです。