algorithm 依多項分配產生抽樣結果

multinomial,多項分配,sampling,抽樣

概念

依照指定機率比如20 30 40 10,累加後產生區間[0,20)、[20,50)、[50,90)、[90,100),區間長度符合機率值,

然後從[0,100)中隨機抽取數字,再判斷落在哪一個區間。

public static void main(String[] args) {
	//指定機率的多項分配
	int[] weights = {20,30,40,10};
	for(int i =0 ;i<1000;i++) {
		System.out.println(multinomial(weights));	
	}
}

/**
 * 傳入做為權重的array,返回選到的index
 */
public static int multinomial(int arr[]) {
	int rtnIndex=-1;
	int sum = Arrays.stream(arr).sum();
	int [] cumulativeArr = getCumulativeArr(arr);
	Random random = new Random();
	
	int randNum = random.nextInt(sum);
	//System.out.println("randNum:"+randNum);
	for(int i =0;i<cumulativeArr.length;i++) {
		if(randNum <cumulativeArr[i]) {
			rtnIndex = i;
			break;
		}
		//System.out.println("loop :"+i);
	}
	
	return rtnIndex;
}

private static int[] getCumulativeArr(int[] arr) {
	int [] rtnArr = new int[arr.length];
	
	rtnArr[0] = arr[0];
	for(int i =1 ;i<arr.length ;i++) {
		rtnArr[i] = arr[i]+rtnArr[i-1];
		//System.out.println("getCumulativeArr:"+rtnArr[i]);
	}
	return rtnArr;
}

Reference