ある整数列からランダムに整数を取り出す。

去年卒業しましたたまのびです。

このブログってOB投稿ありですかね？問題があれば削除してください。

～重複しないように乱数を得る方法～

　整数について乱数を作成すると、数が重複する場合があります。巡回セールスマン問題の巡回経路を決定するときなど、重複する場合問題が発生する場合があります。そんなときにはこれ！！

/*************************************************
関数　：undupRnd(min,max,dest,n)
機能　：最小値min,最大値maxの整数列の中からn個だけ
　　　　無作為に取り出し配列destに格納
戻り値：destの先頭アドレス
備考　：rand()関数を内部で使用
*************************************************/
int *undupRnd(int min,int max,int *dest,int n){
	int i;
	int *array;
	int size = max - min +1;
	if( NULL == dest ){
		fprintf(stderr,"格納先が不正[%s:%s]\n",__FILE__,__LINE__);
		return NULL;
	}
	if( size < n ){
		fprintf(stderr,"取り出す数が取り出す範囲より大きい[%s:%s]\n",__FILE__,__LINE__);
		return NULL;
	}
	if( NULL == (array = (int*)calloc(size,sizeof(int))) ){
		fprintf(stderr,"配列が確保できない[%s:%s]\n",__FILE__,__LINE__);
		return NULL;
	}
	//勢数列の配列を順番に。
	for(i=0;i<size;i++){ array[i] = i+min; }
	
	for(i=0;i<n;i++){
		int index = rand()%(n-i);
		dest[i] = array[index];//抽出
		array[index] = array[n-i-1];//上書き
	}
	free(array);
	
	return dest;
}

簡単にC言語プログラミングしてみました。

実際にコンパイルして使ってみてください。重複しない整数乱数列を生成できます。

このアルゴリズムは至極簡単なものです。

1. 連続する整数列（取り出す対象）を配列に確保する
2. 乱数を用いて取り出す要素の添え字を決める
3. 取り出して格納する。
4. 取り出した要素を配列の端っこの要素で上書き（これで同じ値は取り出されなくなる）
5. 次に添字を選ぶときは範囲を1だけ狭める（これで同じ値は取り出されなくなる

４と５によって同じ値が取り出されるのを阻止しています。

関数中での引数nとsize(max-min+1)が等しい(n=size)のとき、この関数は整数を無作為に並び替える機能を持つと言えます。こう考えると用途は広がりそうですね。どんどん使ってみてください。