去年卒業しましたたまのびです。
このブログって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だけ狭める（これで同じ値は取り出されなくなる
４と５によって同じ値が取り出されるのを阻止しています。
関数中での引数nとsize(max-min+1)が等しい(n=size)のとき、この関数は整数を無作為に並び替える機能を持つと言えます。こう考えると用途は広がりそうですね。どんどん使ってみてください。
