C++で完全順列（Derangement）を数える方法 ― どの要素も元の位置に来ない順列の個数を求める

完全順列（Derangement）とは

完全順列（撹乱順列、Derangement）とは、N 個の数字の順列のうち、「どの数字ひとつとしても元の位置に現れない」ような並び替えのことです。たとえば {1, 2, 3} の完全順列のひとつが {2, 3, 1} です。この並びでは、どの要素も元々の位置から動いています。ここでの目的は、N 個の数字に対して可能な完全順列の個数を求めることです。

これを再帰的な解法で求めていきます。要素数ごとの値は次のとおりです。

• N = 0 … 並び替えの対象が存在しないため 1 を返す
• N = 1 … 数字が 1 つしかなく入れ替えられないため 0 を返す
• N = 2 … 位置の入れ替えは 1 通りだけ（{1, 2} → {2, 1}）なので 1 を返す
• N = 3 … 可能な完全順列は 2 通り（{1, 2, 3} → {2, 3, 1}、{3, 1, 2}）
• N = 4 … 可能な完全順列は 9 通り
• 一般に N 個の場合 … D(N) = (N − 1) × (D(N − 1) + D(N − 2))

配列の各要素に着目した考え方

• インデックス 0 の要素が移動できる位置は n − 1 通りあります。
• インデックス i の要素をインデックス 0 に置く場合は、arr[i] と arr[0] を入れ替えることになり、残りの計算対象は n − 2 個になります。
• インデックス i の要素をインデックス 0 に置かない場合は、n − 1 個の要素それぞれに n − 2 通りの選択肢があります。

図解

入力例

Arr[] = { 1, 2 }

出力例

No. of derangements : 1

説明 ― 1 と 2 の位置はそれぞれインデックス 0 と 1 です。両者が取り得るのは互いの位置を交換する場合だけで、結果は {2, 1} の 1 通りです。

入力例

Arr[] = { 1, 2, 3 }

出力例

No. of derangements : 2

説明 ― 1、2、3 の位置はそれぞれインデックス 0、1、2 です。

1 はインデックス 1 か 2 に、2 はインデックス 0 か 2 に、3 はインデックス 0 か 1 に置くことができます。

したがって {2, 3, 1} と {3, 1, 2} の 2 通りが完全順列となります。

プログラムで使っているアプローチ

• 整数 Num が、扱う数字の個数を保持します。
• 再帰関数 derangements(int N) は数字の個数を引数として受け取り、完全順列の個数を返します。
• N = 0、1、2 に対する return 文はベースケース（基底ケース）を処理しており、あらかじめ計算済みの値 1、0、1 をそのまま返します。
• N > 2 の場合は、次の漸化式にもとづいて derangements() を再帰的に呼び出します。
  (N − 1) × (derangements(N − 1) + derangements(N − 2))

再帰の巻き戻し（バックトラッキング）が始まると、全体の個数が計算され、最終的な結果として返されます。

コード例

#include <bits/stdc++.h>
using namespace std;
int derangements(int N){
    if (N == 0)
        return 1;
    if (N == 1)
        return 0;
    if (N == 2)
        return 1;
    return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}
int main(){
    int Numbers = 5;
    cout<<"Number of Derangements :"<<derangements(Numbers);
}

出力

Number of Derangements :44

補足：計算量について

この素朴な再帰実装では、同じ部分問題が何度も再計算されるため、指数関数的な時間計算量になります。実際、完全順列の個数は 1, 0, 1, 2, 9, 44, 265, … と増えていく「準階乗（subfactorial、!n）」と呼ばれる数列であり、N が大きくなると急激に発散します。実用的な規模の入力を扱う場合は、メモ化（memoization）や動的計画法（DP）を使って D(N−1)、D(N−2) の結果をキャッシュすると、大幅な高速化が期待できます。