取り違えは何通り？

6089 ワード
C codeiq C テキストリンク

出題

一人一台のパソコンを支給されている社員N人全員が、他人のパソコンを使う組み合わせは何通りあるか？

考え方

これは場合の数における完全順列(攪乱順列とも呼ぶ)と言うもの
Nが2～4までなら手動で解いた方が楽だが、それ以上の場合は漸化式を使う必要がある。
もし総当たりで解こうとすれば非常に難問となる。

ここはありがたく過去の偉人の英知にすがる事にします。
完全順列の総数を求める漸化式はこれ。

これを見るとA1 or A2 になるまで再帰的に呼び出せば良い事がわかる。

回答

以上の内容によりこんな感じにしてみた。

/* 完全順列の個数(モンモール数) */
long long montmort_number(int n) {

    if (n == 1) {
        return 0;
    }
    else if (n == 2) {
        return 1;
    }
    return (n - 1) * (montmort_number(n - 1) + montmort_number(n - 2));
}

int main() {
    int i, l, N;
    char s[80];

    for (; ~scanf("%s", s);) {
        l = strlen(s);
        for (N = 0, i = 0; i < l ; i++)
            N = (N * 10) + s[i] - '0';

        sprintf(s, "%lld", montmort_number(N));

        puts(s);
    }
    return 0;
}

[結果]
montmort_number(1) => 0
montmort_number(2) => 1
montmort_number(3) => 2
montmort_number(4) => 9
montmort_number(5) => 44
montmort_number(6) => 265
montmort_number(7) => 1854

感想

4人までなら手動で試すのもありだけど5人以降だと難しいかな。
7人だと1854/5040通りもあるのか。

ソースの動作は再帰を使っているので非常に遅い。
繰り返しの処理を使えればもう少し早くなると思う。