乱数の個数を限定する
Re: 乱数の個数を限定する
最初にそのデータを作成しておいて、ランダムを使って交換を行うようにすればよいと思います。
例えばこんな感じ?
例えばこんな感じ?
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 へにっくす
Re: 乱数の個数を限定する
確かにそうですが、最初に全部シャッフルしなくても、へにっくす さんが書きました:最初にそのデータを作成しておいて、ランダムを使って交換を行うようにすればよいと思います。
〇初期化
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で殴ればいい!(死亡フラグ)
Re: 乱数の個数を限定する
別の感じで無理矢理.
↓のコードは {0が15個,1が5個} という例です.
各乱数結果候補(ここでは0か1)がサイコロを振って出た数で勝負し,勝った奴を結果とします.
>0が10個、1が7個、2が3個
であれば,最初のところを とします.
↓のコードは {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;
}
であれば,最初のところを とします.
Re: 乱数の個数を限定する
素直にカウンタを用いて「各乱数の出る個数を限定する」方法も考えられます。
同じ候補が大量にあるとき、No: 3の方法より空間計算量は優りますが、時間計算量は劣るかもしれません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 乱数の個数を限定する
自分で書いといて何だけど,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;
}
Re: 乱数の個数を限定する
自力でシャッフルしなくても標準ライブラリのstd::random_shuffle (C++03以前)か、std::shuffle(C++11以降)を使った方が良くないか?
Re: 乱数の個数を限定する
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を埋めています。これに関してはもっと賢い方法があるかも?
std::random_shuffleも、std::randに依存する場合があり、std::randと同様に非推奨となります。おそらくこのまま議論が進めば、std::randよりも早くC++1z辺りには削除されます。std::shuffleを使いましょう。
std::fill_nで0が15個、1が5個でstd::arrayを埋めています。これに関してはもっと賢い方法があるかも?
✜ で C ご ✜
: す + 注 :
¦ か + 文 ¦
: ? Is the は :
✜ order C++? ✜
: す + 注 :
¦ か + 文 ¦
: ? Is the は :
✜ order C++? ✜
糸冬
――――――――
制作・著作 NHK
――――――――
制作・著作 NHK
Re: 乱数の個数を限定する
もし個数を限定しないで、だいたいの比で良ければ、以下のようにできます。
25%の確率で1,75%の確率で0になります。
結果は、4,16であったり、3,17であったり、5,15であったり、ランダムですが。
#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;
}
結果は、4,16であったり、3,17であったり、5,15であったり、ランダムですが。
✜ で C ご ✜
: す + 注 :
¦ か + 文 ¦
: ? Is the は :
✜ order C++? ✜
: す + 注 :
¦ か + 文 ¦
: ? Is the は :
✜ order C++? ✜
糸冬
――――――――
制作・著作 NHK
――――――――
制作・著作 NHK
Re: 乱数の個数を限定する
自分のNo: 3の方法では、各候補の残り候補の数にほぼ比例した確率で各候補が出ますが、
No: 5の方法では、残っている候補の中からほぼ等確率で各候補が出ます。
mkaiさんが求めているのはどのような分布の乱数でしょうか?
(「ほぼ」と書いたのは、使用する疑似乱数の精度に依存するからです)
残っている候補の中からほぼ等確率で各候補が出る方式で、
No: 5と違って無駄な乱数生成をしない方法のコードを載せます。
Nを乱数の候補の数として、初期化O(N log N)、クエリ1回あたりO((log N)^2)です。
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で殴ればいい!(死亡フラグ)
Re: 乱数の個数を限定する
各候補の残り候補の数に(ほぼ)比例した確率で各候補を出す乱数を使用する場合でも、
BITを利用することで、空間計算量(≒メモリの使用量) をO(出す乱数の総数)からO(出す乱数の候補の種類数)に減らすことができます。
No: 10で「候補がなくなったらBITからその候補があるという情報を消す」という処理をする代わりに、BITに各候補の残り数を直接入れます。
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で殴ればいい!(死亡フラグ)
Re: 乱数の個数を限定する
私のコードについて補足します。
参考: https://sites.google.com/site/cpprefjp/reference/random
std::random_deviceは、完全な乱数生成エンジンです。ハードウェアのノイズやマウスの動き、CPU温度など、予測不可能な値から乱数を生成するため(実装は処理系定義)、生成される値も予測不可能である完全な乱数です。(ただし、処理系によっては実装の制限により擬似乱数になる可能性はある)
ただしコストが高いので、頻繁に呼び出したりするものではなく、擬似乱数エンジンのシードに使用する事が多いようです。私のコードでもそのように使っています。
std::mt19937が、標準ライブラリで用意されている擬似乱数生成エンジンのひとつです。
メルセンヌツイスター法のエンジンに、デフォルトでパラメータが設定されています。メルセンヌツイスター以外にも線形合同法やキャリー付き減算法などが用意されています。
メルセンヌツイスターは非常に長い周期を持ち、大きな次元で均等分布します。デフォルト設定されているstd::mt19937は627次元であるため、空間的に非常な大きな領域を保持します。周期は219937-1です。
簡単に扱える上、非常に高精度である乱数生成エンジンです。
std::shuffleの第三引数で、乱数生成エンジンを指定できます。ここでメルセンヌツイスターのようなエンジンのオブジェクトを指定することで、シャッフルの精度が変わります。
std::discrete_distributionは、標本分布です。指定した確率列に基づいて離散した確率分布をします。
分布生成エンジンもたくさん用意されているので、目的に合ったエンジンに差し替えれば同じように使えます。
参考: 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++? ✜
: す + 注 :
¦ か + 文 ¦
: ? Is the は :
✜ order C++? ✜
糸冬
――――――――
制作・著作 NHK
――――――――
制作・著作 NHK
Re: 乱数の個数を限定する
へにっくすさん、みけCATさん、usaoさん、hogeさん、nullptrさん
返信ありがとうございます!
思ったより複雑なコードになるのですね…
皆様のコードの意味を理解するのに少し時間がかかるかもしれませんが…
まずは皆様のコードを参考に走らせてみます!
ありがとうございました!
みけCATさん
分布は特に何かの確率分布などに従うことは考慮してないです
0,1からなる数字列を時間発展させるにあたり、初期値の分布としてランダムに0,1を取ることを考えたのですが
ただのランダムでは1の数が毎回変わるので、1の数を固定して発展が見れないかと思いまして…
返信ありがとうございます!
思ったより複雑なコードになるのですね…
皆様のコードの意味を理解するのに少し時間がかかるかもしれませんが…
まずは皆様のコードを参考に走らせてみます!
ありがとうございました!
みけCATさん
分布は特に何かの確率分布などに従うことは考慮してないです
0,1からなる数字列を時間発展させるにあたり、初期値の分布としてランダムに0,1を取ることを考えたのですが
ただのランダムでは1の数が毎回変わるので、1の数を固定して発展が見れないかと思いまして…