プログラミング珠玉--第12章サンプリング問題

2017 ワード

問題の説明:プログラムの入力は2つの整数mとnを含み、ここでmこれらの問題を議論する前に2つの仮説がある:1.大きなランダム整数(mとnよりはるかに大きい)を返す関数bigrand()がある.
2.もう一つの関数randint(i,j)はiを返すことができる.j範囲内で均一に選択されたランダム整数.
解法1:m=2,n=5を仮定し,最初の数0を選択する確率は2/5であり,if(bigrand()%5)<2,<2は0または1しか取れず,確率が2/5であることを示す文で実現できる.しかし、私たちが1を選ぶときは、前に0を選んだかどうかによって決まります.0が選択されている場合は1/4の確率で1を選択し、0が選択されていない場合は2/4の確率で1を選択します.m=nの場合、必ず選択できる(bigrand()%m

select=m
remaining=n
for i=[0,n)
if(bigrand()%remaining)<select
print i
select--
remaining--

分析:ここでは遍歴しています[0,n]を選択し、確率で選択し、selectとremainingを選択した場合は1を減らし、remainingを選択しなかった場合は1を減らす.selectが0に減少した場合、プログラムは実行中であるが、これ以上選択することは不可能であるため、selectが0に減少したときにプログラムが飛び出したことを修正することができる.Knuthは、各サブセットが選択される可能性が等しいことを証明する.
c++実装:

void getknuth(int m,int n){
	for(int i=0;i<n;i++)
		if((bigrand()%(n-i))<m){
			cout<<i<<"
";
			m--;
		}
}

解法2:最初は空の集合にランダム整数を挿入し、個数が十分になるまで挿入します.ここではc++stlのsetを用いて実現する.
setはコンテナで、要素値が一意である.たとえば、次の手順で説明します.

#include<iostream>
#include<set>
using namespace std;
int main(){
	set<int> s;
	s.insert(3);
	s.insert(3);
	cout<<s.size();
	return 0;
}

出力の値は1であり、同じであればset選択は挿入しない.

void getsets(int m,int n){
	set<int> S;
	while(S.size()<m)
		S.insert(bigrand()%n);
	set<int>::iterator i;
	for(i=S.begin();i!=S.end();++i)
		cout<<*i<<endl;
}

解法3:0~n-1を含む配列を順番に乱し、前のm個の要素を並べ替えて出力する.

void genshuf(int m,int n){
	int i,j;
	int *x=new int[n];
	for(i=0;i<n;i++)
		x[i]=i;
	for(i=0;i<m;i++){
		j=randint(i,n-1);
		int t=x[i];
		x[i]=x[j];
		x[j]=t;
	}
	sort(x,x+m);
	for(i=0;i<m;i++)
		cout<<x[i]<<endl;
}

[翻訳]Cocoaの勉強方法

UVA 195 Anagram