ランダムに行を抜き出すプログラム

最近ランダムとは何だろう? と良く考えます。 「でたらめ」、「適当」…などとも言えるのかもしれませんが、例えばこんな問題がありました。

ケーキがあります。
ランダムに 6 つのいちごを乗せてください。

何も考えないで配置すると偏りが出てしまったりします。 ちょうど華道で投げ入れというものと同じで、「ランダムのようで実はランダムでない美しさを楽しむ」というものですが、ランダムというのは難しいのです。

問題を変えてみましょう。

ケーキがあります。
分け隔てなく 6 つのいちごを乗せてください。

6 角形を描くようにいちごを置く場合が多いと思いますが、2 次元や 3 次元ではこういった配置の方がランダムなのではないかと考えることが多い今日この頃です。

さて、今回は ランダムに行を抜き出すプログラムからですが、いくつか例を挙げてみます。

#! /usr/bin/gawk -f
# random_choice.awk

BEGIN {
    srand();

    num = ARGV[1];
    delete ARGV[1];
}

{
    line[NR] = $0;
}

END {
    for (i = 1; i <= num; i++) {
        print line[random(NR)];
    }
}

function random(num) {
    return int(rand() * num + 1);
}

実行するには以下のようにします。

$ ]$ seq 1000 | gawk -f random_choice.awk 10
597
928
209
794
285
789
82
127
255
512

何となく良さそうな気もするのですが、rand() を使っているだけですので、ダブってしまうこともあるという欠点があります。 そこで、以下のような改良を加えます。 これは 配列のシャッフルで使ったシャッフルを用います。

#! /usr/bin/gawk -f
# random_choice_2.awk

BEGIN {
    srand();

    num = ARGV[1];
    delete ARGV[1];
}

{
    line[NR] = $0;
}

END {
    shuffle_array(line);
    for (i = 1; i <= num; i++) {
        print line[i];
    }
}

# 配列をシャッフル
function shuffle_array(arr,    tmp) {
    for (a in arr) {
        num_arr++;
    }

    for (i = num_arr; i >= 1; i--) {
        j = int((i + 1) * rand());

        if (j == 0) {
            j = 1;
        }

        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

シャッフルをしているのでダブりはありません。

もうひとつ awk の配列がハッシュであることを利用して以下のようなものを作ってみました。

#! /usr/bin/gawk -f
# random_choice_3.awk

BEGIN {
    num = ARGV[1];
    delete ARGV[1];
}

{
    line[NR] = $0;
}

END {
    for (i in line) {
        print line[i];
        if (++j >= num) {
            break;
        }
    }
}

意外に良いのではないかと思ったのですが、結果は結構偏ってしまいました。

$ seq 1000 | gawk -f random_choice_3.awk 10
780
781
740
782
741
700
80
783
742
701