プレゼント交換問題
id:Nabetani:20061217:p1 を解いてみる。言語は C。
- まず各参加者がどのグループからプレゼントをもらうか、と言う組み合わせを数える。
- 数えるだけ。記録しない。
- 乱数でその中から一つを選ぶ。
- 組み合わせを数えるときとほぼ同じ事を繰り返して(乱数で決めた数+1)番目のパターン。
- どの参加者からもらうか決める。
という方法(になっているはず)。
思ったこと
- 変数や関数の名前がかっこ悪いのは気にしないでください。
- 人数かグループ数が多くなると、計算に時間がかかる。
- 15人が 5人、4人、3人、2人、1人のグループに分かれている場合、手元のパソコンで 0.4 秒程度。
- 14人が 2人ずつ 7グループに分かれている場合、50〜100 秒程度。
- 20人が 6人、5人、5人、4人のグループに分かれている場合、70〜150 秒程度。
- 参加者 13人全員別のグループなんていうのだと組み合わせが 32bit int の範囲を越えるので、この方法ではきついだろう。
- そういうのはランダムにもらう相手を決めて同じグループだったら計算し直し、のような方法がよさそう。
- このアルゴリズムは人数が多いグループがあるときに速いっぽい。
- 「どのグループからもらうか」の組み合わせが RAND_MAX に近くなると、"(int)(rand()/(RAND_MAX+1.0)*組み合わせ数)" の一様性が怪しく思える。
- ちなみに「2人ずつ 7グループ」は組み合わせの数が RAND_MAX の 1/25 程度。
解答篇読んだ。努力の方向が間違っていた。こっぱずかしい。
以下ソース
#include<stdio.h> #include<stdlib.h> #include<time.h> //人数 #define PERSON 15 //グループの数 #define GROUP 5 int counter; int count_group_pattern(const int *group_list, const int *group_member_num); void get_group_pattern(const int *group_list, int nth, int *present_from_g, const int *group_member_num); void get_pattern(const int *group_list, const int *present_from_g, int *present_from_p, int *group_member_num); void group_member_count(const int *group_list, int *group_member_num); int main() { //0...PERSON-1 の人がどのグループに属しているかのリスト int group_list[PERSON]={0,0,0,0,0,1,1,1,1,2,2,2,3,3,4}; int present_from_g[PERSON], present_from_p[PERSON]; int group_member_num[GROUP]; int pattern_num, nth; int i; srand(time(NULL)); group_member_count(group_list, group_member_num); pattern_num = count_group_pattern(group_list, group_member_num); if(pattern_num==0){ puts("ありません"); return 0; } //printf("%d\n", pattern_num); nth = (int)(rand()/(RAND_MAX+1.0)*pattern_num); get_group_pattern(group_list, nth, present_from_g, group_member_num); get_pattern(group_list, present_from_g, present_from_p, group_member_num); // get_pattern は group_member_num を破壊するので、 // 繰り返したいときは group_member_count で値を計算し直すこと //group_member_count(group_list, group_member_num); for(i=0; i<PERSON; i++){ printf("%c%d->%c%d ", present_from_g[i]+'a', present_from_p[i], group_list[i]+'a', i); } putchar('\n'); return 0; } void group_member_count(const int *group_list, int *group_member_num) { int i; for(i=0; i<GROUP; i++) group_member_num[i]=0; for(i=0; i<PERSON; i++){ group_member_num[group_list[i]]++; } return; } int next_can_present(int point, int group, const int *group_list, const int *present_from_g) { while(point<PERSON && (group_list[point]==group || present_from_g[point]>=0)){ point++; } return point; } void count_group_pattern_r(const int *group_list, const int *group_member_num, int *present_from_g, int group, int g_member, int point) { if(group>=GROUP) { counter++; return; } while((point=next_can_present(point, group, group_list, present_from_g)) <PERSON){ present_from_g[point]=group; if(g_member+1==group_member_num[group]){ count_group_pattern_r(group_list, group_member_num, present_from_g, group+1, 0, 0); }else{ count_group_pattern_r(group_list, group_member_num, present_from_g, group, g_member+1, point); } present_from_g[point]=-1; point++; } return; } int count_group_pattern(const int *group_list, const int *group_member_num) { int present_from_g[PERSON]; int i; counter=0; for(i=0; i<PERSON; i++) present_from_g[i]=-1; count_group_pattern_r(group_list,group_member_num,present_from_g,0,0,0); return counter; } void get_group_pattern_r(const int *group_list, int nth, int *present_from_g, const int *group_member_num, int group, int g_member, int point) { if(group>=GROUP) { counter++; return; } while((point=next_can_present(point,group,group_list,present_from_g)) <PERSON){ present_from_g[point]=group; if(g_member+1==group_member_num[group]){ get_group_pattern_r(group_list, nth, present_from_g, group_member_num, group+1, 0, 0); }else{ get_group_pattern_r(group_list, nth, present_from_g, group_member_num, group, g_member+1, point); } if(nth<counter){ break; } present_from_g[point]=-1; point++; } return; } void get_group_pattern(const int *group_list, int nth, int *present_from_g, const int *group_member_num) { int i; counter=0; for(i=0; i<PERSON; i++) present_from_g[i]=-1; get_group_pattern_r(group_list, nth, present_from_g, group_member_num, 0, 0, 0); return; } void get_pattern(const int *group_list, const int *present_from_g, int *present_from_p, int *group_member_num) { int i, k, p, n, rem; for(i=0; i<PERSON; i++){ present_from_p[i]=-1; } for(i=0; i<PERSON; i++){ rem = group_member_num[group_list[i]]; n=(int)(rand()/(RAND_MAX+1.0)*rem); k=0; p=-1; while(k<=n){ p++; if(present_from_g[p]==group_list[i] && present_from_p[p]<0){ k++; } } present_from_p[p]=i; group_member_num[group_list[i]]--; } return; }
ちょっと修正
--- present.c.orig Wed Dec 27 19:12:15 2006 +++ present.c Wed Dec 27 19:18:46 2006 @@ -12,7 +12,7 @@ void get_group_pattern(const int *group_list, int nth, int *present_from_g, const int *group_member_num); void get_pattern(const int *group_list, const int *present_from_g, - int *present_from_p, int *group_member_num); + int *present_from_p); void group_member_count(const int *group_list, int *group_member_num); int main() @@ -35,10 +35,7 @@ nth = (int)(rand()/(RAND_MAX+1.0)*pattern_num); get_group_pattern(group_list, nth, present_from_g, group_member_num); - get_pattern(group_list, present_from_g, present_from_p, group_member_num); - // get_pattern は group_member_num を破壊するので、 - // 繰り返したいときは group_member_count で値を計算し直すこと - //group_member_count(group_list, group_member_num); + get_pattern(group_list, present_from_g, present_from_p); for(i=0; i<PERSON; i++){ printf("%c%d->%c%d ", present_from_g[i]+'a', present_from_p[i], group_list[i]+'a', i); @@ -75,6 +72,10 @@ { if(group>=GROUP) { counter++; + if(counter<=0){ + fputs("Too many patterns\n",stderr); + exit(1); + } return; } @@ -149,10 +150,12 @@ } void get_pattern(const int *group_list, const int *present_from_g, - int *present_from_p, int *group_member_num) + int *present_from_p) { int i, k, p, n, rem; + int group_member_num[GROUP]; + group_member_count(group_list, group_member_num); for(i=0; i<PERSON; i++){ present_from_p[i]=-1; }
