プレゼント交換

「あなたならどうお書きになります1.0」をやってみた（時間切れだけど）。

完全にランダムで割り当ててから身内に贈っていないか判定するのでは遅いので、一人ずつ身内以外に贈り先を決めていって、途中で身内にしか贈れないことがわかったら最初からやり直し、という風にしてみた。回答には

1. 全部数え上げて、そこから乱数で選ぶ。
2. 適当に作ったパターンが条件に合致していたら終了。
3. ちゃんとやる。全部数え上げたりしない。

とある。Nabetani氏のは理解しきれてないけど、ランダムでソートしたものを総当りっぽい。だから私のはベターな(2)か。

(a)贈っていない人のリスト
(b)各グループの残りの人数
(c)残りの総グループ数
を保持しておくようにした。
たいてい数回の試行で終わるのだが、わざと意地悪な入力をしてみる。
例えばa b c d e f g h i j k:1 k:2 k:3 k:4 k:5 k:6 k:7 k:8 k:9 k:10とか。
身内にしか贈れない判定を入れると数十万回（C/C++だと数秒）で終わるが、入れないと指数関数的に試行回数が増えるので終わらないっぽい。

#include <stdio.h>
#include <time.h>
#include <vector>
#include <deque>
#include <map>

struct Person {
    const char *name;
    int group;
    int send_to;
};
typedef std::vector<Person> People;
typedef std::deque<Person *> Queue;
typedef std::map<int, int> GroupCount;

static bool randomize( const People &people, Queue senders, GroupCount group_count )
{
    int remain_groups = group_count.size();     // number of remain groups
    int receiver;
    for ( receiver = 0; receiver < people.size(); ++receiver ) {
        int group = people[receiver].group;
        if ( remain_groups <= 1 && group == senders[0]->group ) {
            return false;       // no available group to send
        }
        Queue::iterator sender;
        while ( true ) {
            sender = senders.begin() + (rand() % senders.size());
            if ( group != (*sender)->group ) {
                break;      // receiver is found
            }
        }
        (*sender)->send_to = receiver;
        senders.erase( sender );
        if ( --group_count[group] < 1 ) {
            --remain_groups;        // group is decreased
        }
    }
    return true;
}

int main(int argc, char* argv[])
{
    size_t i;

    People people;
    GroupCount group_count;
    for ( i = 1; i < argc; ++i ) {
        if ( isalpha( *argv[i] ) ) {
            int group = tolower(*argv[i]);
            Person person = { argv[i], group };
            people.push_back( person );
            ++group_count[group];
        }
    }
    if ( group_count.size() <= 1 ) {
        fprintf( stderr, "no different groups\n" );
        return 1;
    }

    GroupCount::const_iterator g;
    for ( g = group_count.begin(); g != group_count.end(); ++g ) {
        if ( g->second > (people.size() / 2) ) {
            fprintf( stderr, "no solution\n" );
            return 1;
        }
    }

    Queue senders;
    for ( i = 0; i < people.size(); ++i ) {
        senders.push_back( &(people[i]) );
    }

    srand( time(NULL) );

    size_t tries = 1;
    while ( !randomize( people, senders, group_count ) ) {
        ++tries;
    }

    printf( "tries = %d, result:\n", tries );
    for ( i = 0; i < people.size(); ++i ) {
        printf( "  %s -> %s\n", people[i].name, people[people[i].send_to].name );
    }

    return 0;
}