乱数の個数を限定する

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
mkai

乱数の個数を限定する

#1

投稿記事 by mkai » 9年前

コード:

int i,s[20];
srand(time(0));
for(i=0;i<20;i++)s[i] = rand()%2;
のように、0、1の乱数を作る時、例えば1の数は5個、0が15個のように数を制限することは出来ないのでしょうか?

また、0、1、2の乱数を作る時、同様に0が10個、1が7個、2が3個のように制限することは出来るのでしょうか?

宜しくお願いします。

アバター
へにっくす
記事: 634
登録日時: 11年前
住所: 東京都

Re: 乱数の個数を限定する

#2

投稿記事 by へにっくす » 9年前

最初にそのデータを作成しておいて、ランダムを使って交換を行うようにすればよいと思います。
例えばこんな感じ?

コード:

int i, t, t1, t2, s[20] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1}; // 0が15個、1が5個
srand(time(0));
for (i = 0; i < 20; i++)//とりあえず20回繰り返す
{
	t1 = rand() % 20; // 交換元
	t2 = rand() % 20; // 交換先
	if (t1 != t2) { // 同じ場合は意味がないので、この判定をする
		// 交換。
		t = s[t1];
		s[t1] = s[t2];
		s[t2] = t;
	}
}
written by へにっくす

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 乱数の個数を限定する

#3

投稿記事 by みけCAT » 9年前

へにっくす さんが書きました:最初にそのデータを作成しておいて、ランダムを使って交換を行うようにすればよいと思います。
確かにそうですが、最初に全部シャッフルしなくても、

〇初期化
1. 残っている候補の数を保持する変数を作る(leftとする)
2. 例えば0を3個、1を7個の場合は配列の0,1,2番目に0、3~9番目に1を格納し、leftに10を格納する

〇乱数の生成
1. 0以上left未満の整数をランダムで1個選ぶ。ここではidxとする。
2. 配列のidx番目の値を今回の乱数として返すために保存する
3. 配列のidx番目とleft-1番目を交換する
4. leftの値を1減らす

のようにすればいいと思います。
スマホからの投稿なのでコードは省略します。

コード:

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

/* 0以上max未満の整数をランダムに返す関数 */
int rand_upto(int max) {
	/* 必要ならもっといい実装をしてください */
	return rand() % max;
}

int main(void) {
#ifndef PUTTERN2
	/* 1の数は5個、0が15個 */
	int candidates_left = 20; /* 乱数の候補の残り数 */
	int candidates[20] = { /* 乱数の候補 */
		1, 1, 1, 1, 1,
		0, 0, 0, 0, 0,
		0, 0, 0, 0, 0,
		0, 0, 0, 0, 0
	};
#else
	/* 0が10個、1が7個、2が3個 */
	int candidates_left = 20; /* 乱数の候補の残り数 */
	int candidates[20] = { /* 乱数の候補 */
		0, 0, 0, 0, 0,
		0, 0, 0, 0, 0,
		1, 1, 1, 1, 1,
		1, 1,
		2, 2, 2
	};
#endif
	srand((unsigned int)time(NULL));
	while (candidates_left > 0) {
		int idx = rand_upto(candidates_left--);
		int rand_result = candidates[idx];
		candidates[idx] = candidates[candidates_left];
		/* candidates[candidate_left]はもう利用しないので、交換ではなく1方向のコピーでよい */
		/* candidates[candidate_left] = rand_result; */

		printf("%d ", rand_result);
	}
	putchar('\n');
	return 0;
}
最後に編集したユーザー みけCAT on 2015年1月19日(月) 15:50 [ 編集 1 回目 ]
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1887
登録日時: 11年前

Re: 乱数の個数を限定する

#4

投稿記事 by usao » 9年前

別の感じで無理矢理.
↓のコードは {0が15個,1が5個} という例です.
各乱数結果候補(ここでは0か1)がサイコロを振って出た数で勝負し,勝った奴を結果とします.

コード:

int main(void)
{
	srand(time(0));
	const int nPtn= 2;
	int Left[nPtn] = { 15, 5 };	//残り個数:0が15個,1が5個

	//乱数取得試行回数N=↑のLeft[]の合計
	int N = 0;
	for( int i=0; i<nPtn; i++ )N+=Left[i];

	//N回やる
	for( int i=0; i<N; i++ )
	{
		int result = 0;
		int MaxScore = -1;
		for( int j=0; j<nPtn; j++ )
		{
			if( Left[j]<=0 )continue;

			int score = rand() % Left[j];
			if( MaxScore < score )
			{
				MaxScore = score;
				result = j;
			}
		}
		--Left[result];

		//この回の乱数値を出力
		std::cout << '[' << i << "] : " << result << std::endl;
	}

	//
	std::cout << "enter to quit" << std::endl;
	std::cin.ignore();
	return 0;
}
>0が10個、1が7個、2が3個
であれば,最初のところを

コード:

const int nPtn = 3;
int Left[nPtn] = { 10, 7, 3 };
とします.

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 乱数の個数を限定する

#5

投稿記事 by みけCAT » 9年前

素直にカウンタを用いて「各乱数の出る個数を限定する」方法も考えられます。

コード:

/* 前後は省略 */
int cnum = 2; /* 候補の最大値+1 */
int c[2] = {5, 15}; /* 各候補の残り */
int i;
for(i=0; i<20; i++) {
    int r;
    do {
        r = rand() % cnum;
    } while(c[r]<=0);
    c[r]--;
    printf("%d\n", r);
}
同じ候補が大量にあるとき、No: 3の方法より空間計算量は優りますが、時間計算量は劣るかもしれません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1887
登録日時: 11年前

Re: 乱数の個数を限定する

#6

投稿記事 by usao » 9年前

自分で書いといて何だけど,No.4のだと
多数派が不当に最初の方に固まって選ばれやすい事態になりそうな気がする.

なので,もっと素直に↓

コード:

int main(void)
{
	srand(time(0));
	const int nPtn= 3;
	int Left[nPtn] = { 10, 7, 3 };	//残り個数

	//乱数取得試行回数N=↑のLeft[]の合計
	int N = 0;
	for( int i=0; i<nPtn; i++ )N+=Left[i];

	//N回乱数
	for( int i=0; i<N; i++ )
	{
		int r = rand() % (N-i);

		for( int j=0; j<nPtn; j++ )
		{
			if( r<Left[j] )
			{
				--Left[j];
				std::cout << '[' << i << "] : " << j << std::endl;	//この回の乱数値を出力
				break;
			}
			else
			{	r -= Left[j];	}
		}
	}

	//
	std::cout << "enter to quit" << std::endl;
	std::cin.ignore();
	return 0;
}

hoge

Re: 乱数の個数を限定する

#7

投稿記事 by hoge » 9年前

自力でシャッフルしなくても標準ライブラリのstd::random_shuffle (C++03以前)か、std::shuffle(C++11以降)を使った方が良くないか?

アバター
nullptr
記事: 239
登録日時: 12年前

Re: 乱数の個数を限定する

#8

投稿記事 by nullptr » 9年前

std::randには問題点が多く、現在の規格で非推奨となっており、将来的に削除されます。C++11で追加された<random>ヘッダをインクルードし、擬似乱数エンジンを使いましょう。
std::random_shuffleも、std::randに依存する場合があり、std::randと同様に非推奨となります。おそらくこのまま議論が進めば、std::randよりも早くC++1z辺りには削除されます。std::shuffleを使いましょう。


std::fill_nで0が15個、1が5個でstd::arrayを埋めています。これに関してはもっと賢い方法があるかも?

コード:

#include <algorithm>
#include <random>
#include <array>
#include <iostream>

int main() {
    std::array<int, 20> a;
    std::fill_n( std::fill_n( a.begin(), 15, 0 ), 5, 1 );
    
    std::random_device seed;
    std::shuffle(a.begin(), a.end(), std::mt19937(seed()));

    for( auto&& v : a ){
        std::cout << v;
    }
}
 
 
✜ で C ご ✜
: す + 注 :
¦ か + 文 ¦
?
Is the は :
order C++? ✜
     糸冬   
  ――――――――
  制作・著作 NHK
 
 

アバター
nullptr
記事: 239
登録日時: 12年前

Re: 乱数の個数を限定する

#9

投稿記事 by nullptr » 9年前

もし個数を限定しないで、だいたいの比で良ければ、以下のようにできます。

コード:

#include <random>
#include <array>
#include <iostream>
#include <algorithm>

int main()
{
    std::random_device seed;
    std::mt19937 engine(seed());

    // 確率列を定義
    std::array<double, 2> probabilities = {
        0.75,0.25 
    };

    // 分布オブジェクトを生成
    std::discrete_distribution<std::size_t> dist{
        probabilities.begin(),
        probabilities.end()
    };

    using Result = std::size_t;
    static const size_t NUMBER = 20;
    std::array<Result, NUMBER> result;
    
    for (size_t n = 0; n < NUMBER; ++n) {
        result[n] = dist(engine);
        std::cout << result[n];
    }
    std::cout << std::endl;
    std::cout << "0:" << std::count_if(result.cbegin(), result.cend(), [](Result a){ return a == 0; }) << std::endl;
    std::cout << "1:" << std::count_if(result.cbegin(), result.cend(), [](Result a){ return a == 1; }) << std::endl;
}
25%の確率で1,75%の確率で0になります。
結果は、4,16であったり、3,17であったり、5,15であったり、ランダムですが。
 
 
✜ で C ご ✜
: す + 注 :
¦ か + 文 ¦
?
Is the は :
order C++? ✜
     糸冬   
  ――――――――
  制作・著作 NHK
 
 

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 乱数の個数を限定する

#10

投稿記事 by みけCAT » 9年前

自分のNo: 3の方法では、各候補の残り候補の数にほぼ比例した確率で各候補が出ますが、
No: 5の方法では、残っている候補の中からほぼ等確率で各候補が出ます。
mkaiさんが求めているのはどのような分布の乱数でしょうか?

(「ほぼ」と書いたのは、使用する疑似乱数の精度に依存するからです)

残っている候補の中からほぼ等確率で各候補が出る方式で、
No: 5と違って無駄な乱数生成をしない方法のコードを載せます。
Nを乱数の候補の数として、初期化O(N log N)、クエリ1回あたりO((log N)^2)です。

コード:

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

/* 配列で表現されたBITのidx番目(0-origin)にvalueを加算する */
void bit_add(int bit[], int bit_size, int idx, int value) {
	idx++;
	while (idx <= bit_size) {
		bit[idx - 1] += value;
		idx += idx & (-idx);
	}
}

/* 配列で表現されたBITのidx番目(0-origin)までの和を求める。(idx番目を含む) */
int bit_sum(const int bit[], int idx) {
	int ret = 0;
	if (idx < 0) return 0;
	idx++;
	while (idx > 0) {
		ret += bit[idx - 1];
		idx -= idx & (-idx);
	}
	return ret;
}

/* 0以上max未満の整数をランダムに返す関数 */
int rand_upto(int max) {
	/* 必要ならもっといい実装をしてください */
	return rand() % max;
}

int main(void) {
#ifndef PUTTERN2
	/* 1の数は5個、0が15個 */
	const int candidates_num = 2; /* 乱数の候補の種類数 */
	const int candidates[2] = {1, 0}; /* 乱数の候補 */
	int candidates_left[2] = {5, 15}; /* 各乱数の候補の残り個数 */
	int candidates_bit[2]; /* どの乱数の候補が残っているかを管理するBIT (Binary Indexed Tree) */
#else
	/* 0が10個、1が7個、2が3個 */
	const int candidates_num = 3;
	const int candidates[3] = {0, 1, 2};
	int candidates_left[3] = {10, 7, 3};
	int candidates_bit[3];
#endif
	int i;
	srand((unsigned int)time(NULL));
	/* BITを初期化する */
	for (i = 0; i < candidates_num; i++) candidates_bit[i] = 0;
	for (i = 0; i < candidates_num; i++) {
		if (candidates_left[i] > 0) bit_add(candidates_bit, candidates_num, i, 1);
	}
	for (;;) {
		/* 1個以上残っている乱数の候補の数 */
		int left_candidates = bit_sum(candidates_bit, candidates_num - 1);
		/* 出す乱数の候補 */
		int idx;
		/* 二分探索で使用する変数 */
		int left, right, mid, random_result_idx;
		/* 実際に出た乱数 */
		int random_result;

		if (left_candidates <= 0) {
			/* 出せる乱数が残っていない */
			break;
		}

		/* どの候補を出すかを決定する */
		idx = rand_upto(left_candidates);
		/* 具体的にそれがどの候補に当たるのかを求める */
		left = 0;
		random_result_idx = right = candidates_num - 1;
		while (left <= right) {
			mid = left + (right - left) / 2;
			/* そこまでの和がidxを超える最小の添え字を求める */
			if (idx < bit_sum(candidates_bit, mid)) {
				if (random_result_idx > mid) random_result_idx = mid;
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		/* 出た候補の残り数を1減らす */
		if((--candidates_left[random_result_idx]) == 0) {
			/* 減らした結果その候補が無くなったら、BITからその候補があるという情報を消す */
			bit_add(candidates_bit, candidates_num, random_result_idx, -1);
		}
		/* どの候補かという情報から具体的な候補を求める */
		random_result = candidates[random_result_idx];

		/* 出た乱数を出力する */
		printf("%d ", random_result);
	}
	putchar('\n');
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 乱数の個数を限定する

#11

投稿記事 by みけCAT » 9年前

各候補の残り候補の数に(ほぼ)比例した確率で各候補を出す乱数を使用する場合でも、
BITを利用することで、空間計算量(≒メモリの使用量) をO(出す乱数の総数)からO(出す乱数の候補の種類数)に減らすことができます。
No: 10で「候補がなくなったらBITからその候補があるという情報を消す」という処理をする代わりに、BITに各候補の残り数を直接入れます。

コード:

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

/* 配列で表現されたBITのidx番目(0-origin)にvalueを加算する */
void bit_add(int bit[], int bit_size, int idx, int value) {
	idx++;
	while (idx <= bit_size) {
		bit[idx - 1] += value;
		idx += idx & (-idx);
	}
}

/* 配列で表現されたBITのidx番目(0-origin)までの和を求める。(idx番目を含む) */
int bit_sum(const int bit[], int idx) {
	int ret = 0;
	if (idx < 0) return 0;
	idx++;
	while (idx > 0) {
		ret += bit[idx - 1];
		idx -= idx & (-idx);
	}
	return ret;
}

/* 0以上max未満の整数をランダムに返す関数 */
int rand_upto(int max) {
	/* 必要ならもっといい実装をしてください */
	return rand() % max;
}

int main(void) {
#ifndef PUTTERN2
	/* 1の数は5個、0が15個 */
	const int candidates_kind_num = 2; /* 乱数の候補の種類数 */
	const int candidates[2] = {1, 0}; /* 乱数の候補 */
	const int candidates_num[2] = {5, 15}; /* 各乱数の候補の個数 */
	int candidates_bit[2]; /* どの乱数の候補が残っているかを管理するBIT (Binary Indexed Tree) */
#else
	/* 0が10個、1が7個、2が3個 */
	const int candidates_kind_num = 3;
	const int candidates[3] = {0, 1, 2};
	const int candidates_num[3] = {10, 7, 3};
	int candidates_bit[3];
#endif
	int i;
	srand((unsigned int)time(NULL));
	/* BITを初期化する */
	for (i = 0; i < candidates_kind_num; i++) candidates_bit[i] = 0;
	/* BITに各乱数の候補の残り数を加える */
	for (i = 0; i < candidates_kind_num; i++) {
		bit_add(candidates_bit, candidates_kind_num, i, candidates_num[i]);
	}

	for (;;) {
		/* 乱数の候補の残り数 */
		int left_candidates = bit_sum(candidates_bit, candidates_kind_num - 1);
		/* 出す乱数の候補 */
		int idx;
		/* 二分探索で使用する変数 */
		int left, right, mid, random_result_idx;
		/* 実際に出た乱数 */
		int random_result;

		if (left_candidates <= 0) {
			/* 出せる乱数が残っていない */
			break;
		}

		/* どの候補を出すかを決定する */
		idx = rand_upto(left_candidates);
		/* 具体的にそれがどの候補に当たるのかを求める */
		left = 0;
		random_result_idx = right = candidates_kind_num - 1;
		while (left <= right) {
			mid = left + (right - left) / 2;
			/* そこまでの和がidxを超える最小の添え字を求める */
			if (idx < bit_sum(candidates_bit, mid)) {
				if (random_result_idx > mid) random_result_idx = mid;
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		/* 出た候補の残り数を1減らす */
		bit_add(candidates_bit, candidates_kind_num, random_result_idx, -1);
		/* どの候補かという情報から具体的な候補を求める */
		random_result = candidates[random_result_idx];

		/* 出た乱数を出力する */
		printf("%d ", random_result);
	}
	putchar('\n');
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
nullptr
記事: 239
登録日時: 12年前

Re: 乱数の個数を限定する

#12

投稿記事 by nullptr » 9年前

私のコードについて補足します。
参考: https://sites.google.com/site/cpprefjp/reference/random

std::random_deviceは、完全な乱数生成エンジンです。ハードウェアのノイズやマウスの動き、CPU温度など、予測不可能な値から乱数を生成するため(実装は処理系定義)、生成される値も予測不可能である完全な乱数です。(ただし、処理系によっては実装の制限により擬似乱数になる可能性はある)
ただしコストが高いので、頻繁に呼び出したりするものではなく、擬似乱数エンジンのシードに使用する事が多いようです。私のコードでもそのように使っています。

std::mt19937が、標準ライブラリで用意されている擬似乱数生成エンジンのひとつです。
メルセンヌツイスター法のエンジンに、デフォルトでパラメータが設定されています。メルセンヌツイスター以外にも線形合同法やキャリー付き減算法などが用意されています。


メルセンヌツイスターは非常に長い周期を持ち、大きな次元で均等分布します。デフォルト設定されているstd::mt19937は627次元であるため、空間的に非常な大きな領域を保持します。周期は219937-1です。
簡単に扱える上、非常に高精度である乱数生成エンジンです。

std::shuffleの第三引数で、乱数生成エンジンを指定できます。ここでメルセンヌツイスターのようなエンジンのオブジェクトを指定することで、シャッフルの精度が変わります。

std::discrete_distributionは、標本分布です。指定した確率列に基づいて離散した確率分布をします。
分布生成エンジンもたくさん用意されているので、目的に合ったエンジンに差し替えれば同じように使えます。
 
 
✜ で C ご ✜
: す + 注 :
¦ か + 文 ¦
?
Is the は :
order C++? ✜
     糸冬   
  ――――――――
  制作・著作 NHK
 
 

mkai

Re: 乱数の個数を限定する

#13

投稿記事 by mkai » 9年前

へにっくすさん、みけCATさん、usaoさん、hogeさん、nullptrさん
返信ありがとうございます!

思ったより複雑なコードになるのですね…
皆様のコードの意味を理解するのに少し時間がかかるかもしれませんが…
まずは皆様のコードを参考に走らせてみます!
ありがとうございました!

みけCATさん
分布は特に何かの確率分布などに従うことは考慮してないです
0,1からなる数字列を時間発展させるにあたり、初期値の分布としてランダムに0,1を取ることを考えたのですが
ただのランダムでは1の数が毎回変わるので、1の数を固定して発展が見れないかと思いまして…

閉鎖

“C言語何でも質問掲示板” へ戻る