数値を無作為に分配するアルゴリズム

Question

数値を無作為に分配するアルゴリズムを考えています。
かなりの回数実行する予定なので、ある程度速いアルゴリズムを求めています。

数値を無作為に分配というのは、10であれば
3,3,4や9,0,1や2,7,1のように分配することを指しています。

正規分布に従う手法であれば(タイトルから少しそれますが)以下リンク先の手法で実装できそうですが、処理負荷が高そう(平方根,sin,cos...)なので他を探しています。
Box-Muller法を用いて正規分布に従う分配を行う - Qiita

おそらくかなり偏った値になりますが、現状考えているのは、
1番目を「010のランダムな値」
n番目を「010-(1~n番目にでた合計値)のランダムな値」とする手法です。

他にいい感じのアルゴリズムや、このような要件で一般的に使用されているアルゴリズムがありましたら、教えていただけると幸いです。

Comments

[swordone]

リンク先の話は「正規分布に従って」、つまり「平均値に近い値ほど高い確率で分配される」分配法です。
タイトルの「無作為に」には適しません。

[quickquip]

結果に0が入っていると現実的には無理じゃありませんか?
9, 0, 0, 0, 0, (100億個の0が並んでいる), 1
が《0でない確率で》出現しなければなりませんよね?
（数学的には確率0ですが）

まあ、分割は n-1 までとして、3を処理したときに
(3),(1, 2),(2, 1),(3, 0),(0, 3),(1, 1, 1),(1, 2, 0),(2, 1, 0),(0, 1, 2),(0, 2, 0),(2, 0, 1),(1, 0, 2),(3, 0, 0),(0, 3, 0),(0, 0, 3)
が「全部同じ確率で出てくる」ことを期待しているのかどうかは気になりますね。

Answer 1

0以上の整数で分配するという前提で回答します。
重複組み合わせの考え方を利用すると、
「分配の仕方」は「仕切りの入れ方」ととらえることができます。
そこで、「仕切りを入れる場所」として、0以上(分配する数+分配する個数-1)未満の乱数を
重複しないように(分配する個数-1)個取れば、どの分け方も等確率で得られます。
例えば、例の場合、つまり10を3つに分配する場合、10+3-1=12なので、
0~11の12個から乱数を2つ取得します。
乱数で得られた位置に仕切りを入れることで、分配の仕方が以下のように対応します。
(位置を示す番号は16進表記)

        0 1 2 3 4 5 6 7 8 9 A B
3,7  -> o o o | o o o | o o o o -> 3,3,4
9,10 -> o o o o o o o o o | | o -> 9,0,1

重複のないようにするには、0~(分配する数+1)の配列などを作って、
シャッフルするかフィッシャー・イェーツの方法を利用するのが確実になると思いますが、
分配する数より分配する個数が十分少なければ、逐次乱数を取り出して重複チェックするのでも
十分実用に足りると思います。

Javaしかできないので、Javaで実装してみました。
仕切りが〇より多くなる場合は、逆に〇を入れる位置を考える、という考え方をしています。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(Arrays.toString(randomSplit(10,3)));
        }
    }
    
    private static int[] randomSplit(int n, int p) {
        int r = p - 1;
        int total = n + r;
        boolean wall = total > r * 2;
        if (!wall) {
            r = n;
        }
        BitSet set = new BitSet(total);
        while (set.cardinality() < r) {
            set.set((int)(Math.random() * total));
        }
        if (!wall) {
            set.flip(0, total);
        }
        
        int[] result = new int[p];
        int prev = 0;
        for (int i = 0; i < r; i++) {
            int next = set.nextSetBit(prev);
            result[i] = next - prev;
            prev = next + 1;
        }
        result[r] = total - prev;
        return result;
    }
}

実行結果(10回ループしています)

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

Comments

[mamyonya768]

ご回答ありがとうございます！
ソースコードまでありがとうございました。

[episteme]

正規分布うんぬんは関係なかったってことですか?

Answer 2

逆に考えよう。平方根や三角関数が速ければよいのだと。

というわけでこちら。
高速三角対数指数関数
fast sqrt
どこまで偏りが出るかは未知数ですが、用途次第だと思います。少なくとも下手にアルゴリズム考えるよりはよいかと。あとメルセンヌツイスター自体が遅いというのもあるので X or shift 使って高速化しちゃいましょう。
Xorshift - Wikipedia

三角関数・平方根に関してはメモリが許せばテーブル化という方法も考えられます。ある値に対しての sin はいくつっていうのを予め配列にしておくのです。そして値が飛んできたら適当に一次近似して値を出すと。メモリが許せば許すほど精度が高くなる方法です。その割にスピードも出るので検討の余地はありかと。

いずれにせよ既存手法の高速化がベターかなと思います。

Comments

[mamyonya768]

既存手法の高速化は考えていませんでした。
ご回答ありがとうございました！