足して100になるような乱数のアルゴリズム

質問

次のような、8つの変数にそれぞれランダム(0から100まで)に発生させた数を入れて
毎回合計で100になるようにしたいです。

a[0] = 12;
a[1] = 21;
a[2] = 8;
a[3] = 30;
a[4] = 0;
a[5] = 14;
a[6] = 5;
a[7] = 10;

もう1回実行したとしても

a[0] = 2;
a[1] = 14;
a[2] = 62;
a[3] = 5;
a[4] = 0;
a[5] = 0;
a[6] = 1;
a[7] = 16;

と合計で100になります。

a[0] = 0;
a[1] = 0;
a[2] = 100;
a[3] = 0;
a[4] = 0;
a[5] = 0;
a[6] = 0;
a[7] = 0;

と滅多にありないですけど、このようになる可能性もあると思います。
このような乱数を発生させるためにはどのようなアルゴリズムになるのでしょうか？

回答No.4

麻野 なぎ（@AsanoNagi） · ベストアンサー

シンプルなアルゴリズムとしてはこんなのもあります。
（ソートが絡みますが）

１．配列 b[9] を準備します（b[8] でなくて）
２．b[0] = 0, b[8] = 100
３．b[2] ～ b[7] には、0 ～ 100 までの乱数をセットします。
４．b[2] ～ b[7] を昇順にソートします。
５．a[0] = b[1] - b[0];
以下、a[n - 1] = b[n] - b[n -1]; です。

この問題は、本質的には 100個のボールを８このグループに分けることに相当します。
言い換えれば、ボールを100個並べて、ランダムな７カ所に区切りを入れることになります。
それぞれの、区切りの間に存在するボールの数が、足して100になる乱数になります。
ソートが難しいかもしれませんが、 qsort() という標準関数が使えますから、ソートすること自体は、１行でできます。

お礼

ご返答ありがとうございます。
ほぼ理想とする結果がでました。ありがとうございます。
あとはほんとに70（50以上でも）以上が現れるものなのかどうかだけなんですけど、
AsanoNagiさんはどうお考えでしょうか？

回答No.8

麻野 なぎ（@AsanoNagi）

No.4 です。
あと、本質的には、乱数として考えると、乱数の数が８個と大きいので、足して100という条件の中では案外偏った組み合わせが得られにくい気はします。
３個かできれば、２個だと時々ばらついた乱数が出てきそうな気はします。（未確認です）

お礼

ご返答ありがとうございます。
実際に乱数の数を減らして試しみたのですが、
確かに少なくなるほど、ばらつきが大きくなるような気がします。

回答No.7

麻野 なぎ（@AsanoNagi）

No.4 です。
このアルゴリズムでは、大きな数字（50 以上とか 70 以上）は、でないことはないけれど非常にまれ……です。

たとえば、70 が出るためには、もとになる方の（ボールの列をぶった切る方の）乱数が、 0, 1, 10, 80, 82, 90, 92 94, 100 のようにかなり偏ったものになる必要があります。
もとの乱数として一様乱数を仮定してしまうと、普通は、偏った乱数ににはならないので、結果として、そこそこ平均的な数値が出てしまうということになります。（その代わり、０ばっかりというような偏った乱数は出てきにくいということになります）

原理自体は単純なので、もとになる方の乱数を偏らせてとれば、（たとえば、平均 10 の乱数と 平均 90 の乱数を使うなど）ある程度の特性持たせることはできます。
ただ、どういう乱数で生成するとどういう乱数が結果として得られるかが、なかなか直感的にわかりにくいのが難点です。

回答No.6

Werner

数学的に証明したわけではないけど、
直感的に今まで出てきてる中だとANo.4のアルゴリズムが一番良いと思う。
ちょっと条件は違ってたけど昔似たようなアルゴリズムを考えたことがあります。
(ボールでたとえるなら、100個のボール2組をそれぞれ
8個のグループに分けて互い違いに並べるような感じ。)

----------------------------------------
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int comp(const void *a, const void *b){
　return *(int*)a - *(int*)b;
}

int main(void){
　int i;
　int sep[9];

　srand((unsigned int)time(NULL));
　sep[0] = 0;
　sep[8] = 100;
　for(i=1;i<8;i++){
　　sep[i] = rand() % 101;
　}
　qsort(sep+1, 7, sizeof(int), comp);
　for(i=0;i<8;i++){
　　printf("a[%d] = %d;\n", i, sep[i+1] - sep[i]);
　}
　return 0;
}
----------------------------------------

> ANo.5
シャッフルするなら何回もかき混ぜるようなやり方をしなくても
Fisher-Yates法(ANo.3でyaemon_2006さんがやってるやり方)で良いと思う。
速くてシンプルだし全組み合わせが等確率で出現するようにシャッフルできるはず。

回答No.5

Oh-Orange

★回答者No.1です。
＞ところで、Oh-Orangeさんのやり方も思いついたのですけれど、
＞なんとなく一様性が失われていないか不安になったりしました。
＞例えばa[0]はいいのですけれど、a[7]には小さめの値が入る確率が高いとかないのでしょうか。
・私もそれは予想していましたよ。
　さっき実際に試してみましたが、予想通り出来が悪いですね。
　a[0]～a[3]に大きい数が集中しています。
　でも0が2、3個連続して出ているためa[0]～a[7]を適当に
　シャッフルすれば単純なアルゴリズムで使えるのではないでしょうか。
　※aemon_2006さんのロジックがそれなのかも。良くソース見ていないけど。
・とりあえず自分で試したシャッフル付き、なしのサンプルを載せておきます。

サンプル:
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

// 記号定数
#define MAX_TABLE　　(8)

// シャッフル
static void Shuffle( int table[], int size )
{
　int pos, rnd, loop, swap;

　for ( loop = (rand() % 100) ; loop > 0 ; loop-- ){
　　for ( pos = 0 ; pos < size ; pos++ ){
　　　rnd = (rand() % size);
　　　swap = table[ pos ];
　　　table[ pos ] = table[ rnd ];
　　　table[ rnd ] = swap;
　　}
　}
}

// 分割乱数
static void OhOrange( int table[], int size )
{
　int i, rnd, max = 100;

　for ( i = 0 ; i < (size - 1) ; i++ ){
　　table[ i ] = rnd = (rand() % max);
　　max -= rnd;
　}
　table[ i ] = max;
}

// メイン関数
int main( void )
{
　int i, table[ MAX_TABLE ];

　srand( (unsigned int)time(NULL) );

　for ( ; ; ){
　　OhOrange( table, MAX_TABLE );
　　Shuffle( table, MAX_TABLE );
　　system( "CLS" );

　　for ( i = 0 ; i < MAX_TABLE ; i++ ){
　　　printf( "a[%d] = %d\n", i, table[i] );
　　}
　　printf( "\n" );
　}
　return 0;
}
工夫すればもっと良くなると思います。
問題はどんなものに利用するのか。
それによりアルゴリズムも変わると思います。

回答No.3

yaemon_2006

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define rndm(n) (int)((n + 1) * (rand() / (RAND_MAX + 1.0)))

void shuffle(int *a, int anum)
{
int i, j, k;

for(i = anum - 1; i; i --){
j = rndm(i);
k = a[i];
a[i] = a[j];
a[j] = k;
}
}

int main(void)
{
int a[8], i, j, n, m;

srand(time(NULL));
for(j = 0; j < 20; j ++){
n = 100;
for(i = 0; i < 7; i ++){
if(n == 0) a[i] = 0;
else a[i] = rndm(n);
n -= a[i];
}
a[7] = n;
shuffle(a, 8);
for(i = 0; i < 8; i ++){
printf("%3d ", a[i]);
}
putchar('\n');
}
return 0;
}

お礼

ご返答ありがとうございます。
試してみたのですが、今度は逆に幅広く散らばっているのですが
0の出現回数が多い（平均2個以上）気がします。

さきほどから
一体こちらがどのような散らばり方を希望してるか分かりずらいと思いますが、
100回の試行中、平均で、40以上が5個ぐらい、70以上が2、3個かな？？
大体ですけど、、、
ただ自分の確率に対する認識がほとんどないので
そのように確率がなるものかというのは自信ないです・・・

回答No.2

dummyplug

ご自分でも何か考えてみました？
いろいろアルゴリズムはありそうです。仮に二つほど。
1)
r[0]からr[7]に乱数を入れる。（合計は100とは限らない）
Tにr[0]からr[7]の合計を入れる
a[i]に100*r[0]/Tを入れる
つまり、合計値100に対する比率を乱数で決める、という方法です。
a[i]が整数になるとは限らない、というかならないことが多いと思うのでそこは一工夫。

2)
仮にa[i]に12または13をいれて合計が100になるようにしておく（本当は均等に分けて12.5にしたいけど、一応整数にするということで。）
0以上7以下の乱数を二つ生成する。それをrとpとする
a[r]が0でなければ1を引き、さらにa[p]に1を加える
この操作を何回も適当な回数だけ繰り返す
つまり、合計が100になるように維持しながら8つのビン(a[i])の中身をランダムに移し替えていくというやり方です。
何回くらい繰り返すと十分にばらつくかは計算できそうですので考えてみてください。

-----
ところで、Oh-Orangeさんのやり方も思いついたのですけれど、なんとなく一様性が失われていないか不安になったりしました。例えばa[0]はいいのですけれど、a[7]には小さめの値が入る確率が高いとかないのでしょうか。
私は頭悪いので直観でそんな気がしたようなしないような感じです。誰かわかる人がいたら「そんなことはない（一様にばらつく）」とか教えてくれるとよいのですが。

お礼

ご返答ありがとうございます。
＞ご自分でも何か考えてみました？
考えれば考えるほど（浅い考えですけど）混乱してくるような感じで・・・
自分としては、70や80などの数もたまには出てほしいと思ってるのですが、
はたしてそれが一様に散らばっていることと矛盾しないかという気もしますし・・・

dummyplugさんの1)と2)を数千回ループさせて試してみて
理想に近い結果がでたのですが、
ただ40以上がほとんど（全試行中1、2回あるぐらい）現れないので
もう少し大きい数字が出てもいいかなという気はします。

回答No.1

Oh-Orange

★単純な方法
・(1)0～100まで乱数発生⇒12が出た。
　(2)0～(100-12)つまり0～88まで乱数発生⇒21が出た。
　(3)0～(88-21)つまり0～67まで乱数発生⇒8が出た。
　(4)0～(67-8)つまり0～59まで乱数発生⇒30が出た。
　(5)0～(59-30)つまり0～29まで乱数発生⇒0が出た。
　(6)0～(29-0)つまり0～29まで乱数発生⇒14が出た。
　(7)0～(29-14)つまり0～15まで乱数発生⇒5が出た。
　(8)(15-5)つまり10を使う。
　こんな方法があります。
・0、0、100、0、0、0、0、0は工夫します。
　つまり0が7つ出るための乱数を発生させます。→仮に1/100の確率とする。
　そして適当な回数で100を出す。
・2、14、62、5、0、0、1、16の場合も対応するために0が2個(任意個)の
　確率を出し条件が揃ったときに6回発生させて2回は0とする。
　このようにすれば0の個数により出やすい、出にくい確率を決めれば
　バリエーションが生まれると思います。
　※普通の擬似乱数を使って同じ数が連続することはまれなのでこのような工夫をする。

お礼

ご返答ありがとうございます。
なるほど、乱数そのものにも工夫が必要なんですね。